問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2192思路:
原本以為是類似于PKU 1936的簡單題，結(jié)果Sample測試不過，發(fā)現(xiàn)對于像cat, tree這樣包含相同字母(這里是t)的例子需要回溯，于是DFS，這樣結(jié)果雖然正確了，但是卻TLE...
準(zhǔn)確的做法是動態(tài)規(guī)劃，艾，今天三題沒有一個是自己想出來的...悲劇...
詳細(xì)的狀態(tài)轉(zhuǎn)化方程見代碼注釋
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 201
5 char first[MAX_LEN+1], second[MAX_LEN+1];
6 char final[MAX_LEN*2];
7 int flen, slen, tlen;
8 int table[MAX_LEN][MAX_LEN];
9
10 /*
11 * f[i][j] represent whether final[1..i+j] could be formed from first[1..i] and second[1..j]
12 * f[i][j] is true if:
13 * a. final[i+j]==first[i] && f[i-1][j] is true, or
14 * b. final[i+j]==second[j] && f[i][j-1] is true
15 */
16 int
17 dp()
18 {
19 int i, j, mark;
20 mark = 1;
21 for(i=1; i<=flen; i++) {
22 if(first[i]==final[i] && mark)
23 table[i][0] = 1;
24 else {
25 table[i][0] = 0;
26 mark = 0;
27 }
28 }
29 mark = 1;
30 for(j=1; j<=slen; j++) {
31 if(second[j]==final[j] && mark)
32 table[0][j] = 1;
33 else {
34 table[0][j] = 0;
35 mark = 0;
36 }
37 }
38 for(i=1; i<=flen; i++) {
39 for(j=1; j<=slen; j++) {
40 if((final[i+j]==first[i]&&table[i-1][j]) || (final[i+j]==second[j]&&table[i][j-1]))
41 table[i][j] = 1;
42 else
43 table[i][j] = 0;
44 }
45 }
46 return table[flen][slen];
47 }
48
49 int
50 main(int argc, char **argv)
51 {
52 int tests, cnt=0;
53 scanf("%d", &tests);
54 while(tests--) {
55 scanf("%s %s %s", first+1, second+1, final+1);
56 flen = strlen(first+1);
57 slen = strlen(second+1);
58 tlen = strlen(final+1);
59 printf("Data set %d: %s\n", ++cnt, dp()?"yes":"no");
60 }
61 }