HDU 1501（dp46）

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; bool dp[205][205]; char str1[205],str2[205],str3[410]; int main() { int T; scanf("%d",&T); str1[0]=str2[0]=str3[0]='0'; int cas=1; while(T--) { int i,j; cin>>str1+1; cin>>str2+1; cin>>str3+1; int k1,k2,k3; k1=strlen(str1)-1; k2=strlen(str2)-1; k3=strlen(str3)-1; for(i=1;i<=k1;i++) { if(str1[i]==str3[i]) dp[i][0]=true; else dp[i][0]=false; } for(i=1;i<=k2;i++) { if(str2[i]==str3[i]) dp[0][i]=true; else dp[0][i]=false; } for(i=1;i<=k1;i++) { for(j=1;j<=k2;j++) { dp[i][j]=(dp[i-1][j]&&str1[i]==str3[i+j]||dp[i][j-1]&&str2[j]==str3[i+j]); } } printf("Data set %d: ",cas++); if(dp[k1][k2]) printf("yes\n"); else printf("no\n"); } return 0; }