本文主要是介绍poj 2192 zipper,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今天突然发现我做了这道题,印象不大 ,但是一看题意 感觉很经典 ,所以决定写一下结题报告
首先这道题的题意是 给你三个字符串,前两个给你弄一下,然后可以构成一个字符串
,但是你要知道这个条件是
他们两个组成最后的字符串时不能改变先后顺序</p><p>得出两个状态方程
dp[i][j]表示这个前i个字符和前j个字符是否会构成s3的前i+j个字符
(1)dp[i][j]=(dp[i-1][j]&&s1[i]==s3[i+j])?ture:flase
(2)dp[i][j]=(dp[i][j-1]&&s2[j==s3[i+j])?true:flase
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;char s1[500],s2[500],s3[500];
int dp[500][500];int main()
{int t,i,j,k,len1,len2,len3,cas = 1 ;scanf("%d",&t);while(t--){scanf("%s%s%s",s1+1,s2+1,s3+1);len1 = strlen(s1+1);len2 = strlen(s2+1);len3 = strlen(s3+1);memset(dp,0,sizeof(dp));for(i = 1; i<=len1; i++){if(s1[i] == s3[i])dp[i][0] = 1;else break;}for(i = 1; i<=len2; i++){if(s2[i] == s3[i])dp[0][i] = 1;else break;}for(i = 1; i<=len1; i++){for(j = 1; j<=len2; j++){if(s3[i+j] == s1[i] && dp[i-1][j])dp[i][j] = 1;if(s3[i+j] == s2[j] && dp[i][j-1])dp[i][j] = 1;}}printf("Data set %d: ",cas++);if(dp[len1][len2])printf("yes\n");elseprintf("no\n");}return 0;
}
这篇关于poj 2192 zipper的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!