字串组合

Description

中午的阳光真好，zzy建完仓库后准备做一顿烧烤犒劳一下自己，于是他拿来了一桶菜和一桶肉，并且打开了百度找到了一张串好的烤串图片。不过装菜和肉的桶太小咯，每次只能从桶顶（最左边）拿食材。zzy想知道他能否构成图片上的烤串。

Input

第一行输入组数t(t<=500) 之后的t行，每行有3个字符串，前两个字符串长度不超过200，第三个字符串长度为前两个字符串长度之和。前两个字符串分别代表了肉和蔬菜，第三个字符串代表了网上图片。每个字符串由大小写字母构成。

Output

每行输出当前组数和能否构成图片，能则输出"Data set t: yes"，不能则输出"Data set t: no"。

Sample Input Copy

3 cat tree tcraete cat tree catrtee cat tree cttaree

Sample Output Copy

Data set 1: yes Data set 2: yes Data set 3: no

这个题还是一个要打表的题；（1代表可以替换，0代表不可以，我们要从（0，0）开始，所以要先定义dp[0][0]=1；

　　cat　　　cat　　　cat　1000　　1111　　1100t1100　t0010　t0100r0110　r0011　r0000e0011　e0001　e0000e0001　e0001　e0000

这三个表呢分别对应前三个样例，一般入门这种题表打出来公式也就出来了，可是作为菜鸡的我，想了好久才想通，大佬一眼就能看出来的东西；我们每次比较的都是当前所在位置的下面，这样当遇到0的时候，我们就直接可以跳过，所以每次要用dp[i

][j+1] or dp[i+1][j] 与c[i+j+1]比较， i（j）表示a（b）中我已经比较到了第i（j）个前i+j都已经比较完了，所以就可以直接得到当前c应该比较字母所在的位置。

#include<stdio.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<math.h> #include<string.h> #include<queue> #include<string.h> using namespace std; int dp[210][210]; char a[210],b[210],c[210]; int main() { int t; scanf("%d",&t); int k=1; while(t--) { scanf("%s%s%s",a+1,b+1,c+1); memset(dp,0,sizeof(dp)); int len1=strlen(a+1); int len2=strlen(b+1); int len3=strlen(c+1); dp[0][0]=1; for(int i=0; i<=len1; i++) { for(int j=0; j<=len2; j++) { if(dp[i][j]==1) { if(a[i+1]==c[i+1+j]) dp[i+1][j]=1; if(b[j+1]==c[i+1+j]) dp[i][j+1]=1; } } } printf("Data set %d: ",k++); if(dp[len1][len2]==1) printf("yes\n"); else printf("no\n"); } return 0; }