ytu oj 动态规划进阶题目之Zipper

2019-04-14 21:13发布

站内文章 / 模拟电子
17212 0 1120
#include #include #include #define maxn 1000010 using namespace std; int dp[204][204]; //dp[i][j]代表s1 前i位 和s2前 j位 能否组成s前 i+j位 int main() { int t; scanf("%d%*c",&t); for(int cnt=1;cnt<=t;cnt++) { char s[409],s1[204],s2[204]; scanf("%s %s %s",s1+1,s2+1,s+1); int len1,len2; len1=strlen(s1+1); len2=strlen(s2+1); memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=0;i<=len1;i++) for(int j=0;j<=len2;j++) { if(i+j==0)continue; if(s1[i]==s[i+j]&&dp[i-1][j]==1)dp[i][j]=1; if(s2[j]==s[i+j]&&dp[i][j-1]==1)dp[i][j]=1; } printf("Data set %d: ",cnt); if(dp[len1][len2])printf("yes "); else printf("no "); } return 0; }

热门文章