POJ 2192 Zipper
ただのDPのはずかstrlen()多用しすぎててTLEにになっていた。
気をつけよう。
#include <cstdio> #include <string.h> #include <iostream> using namespace std; char a[202],b[202],c[404]; bool dp[202][202]; int main(){ int n; cin >> n; int co = 1; while(n--){ memset(dp, 0, sizeof(dp)); scanf("%s%s%s",a,b,c); int alen = strlen(a); int blen = strlen(b); if(a[0] == c[0])dp[1][0] = true; if(b[0] == c[0])dp[0][1] = true; for(int i = 2;i <= alen;i++){ if(a[i-1] == c[i-1] && dp[i-1][0] == true)dp[i][0] = true; } for(int i = 2;i <= blen;i++){ if(b[i-1] == c[i-1] && dp[0][i-1] == true)dp[0][i] = true; } for(int i = 1;i <= alen;i++){ for(int j = 1;j <= blen;j++){ if(a[i-1] == c[i+j-1] && dp[i-1][j] == true){ dp[i][j] = true; }else if(b[j-1] == c[i+j-1] && dp[i][j-1] == true){ dp[i][j] = true; } } } if(dp[alen][blen] == true){ printf("Data set %d: yes\n",co); }else{ printf("Data set %d: no\n",co); } co++; } return 0; }