poj2192 Zipper 两个字符串是否能构成第三个
//dp[i][j]表示s1串的前i个字符和s2的前j个字符能否组成str的前i+j个字符//dp[i][j]只能由dp[i-1][j]和dp[i][j-1]转移过来#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>#include<string.h>using namespace std;char s1[205];char s2[205];char str[410];int dp[205][205];int main(){ int t; int count=1; scanf("%d",&t); while(t--) { scanf("%s%s%s",s1,s2,str); memset(dp,0,sizeof(dp)); int l1=strlen(s1); int l2=strlen(s2); for(int i=1;i<=l1;i++) if(s1[i-1]==str[i-1]) dp[i][0]=1; for(int j=1;j<=l2;j++) if(s2[j-1]==str[j-1]) dp[0][j]=1; for(int i=1;i<=l1;i++) for(int j=1;j<=l2;j++) { if(s1[i-1]==str[i+j-1]&&dp[i-1][j]) dp[i][j]=1; if(s2[j-1]==str[i+j-1]&&dp[i][j-1]) dp[i][j]=1; } printf("Data set %d: ",count++); if(dp[l1][l2]==1) puts("yes"); else puts("no"); }}