問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2192思路:
原本以為是類似于PKU 1936的簡單題，結果Sample測試不過，發現對于像cat, tree這樣包含相同字母(這里是t)的例子需要回溯，于是DFS，這樣結果雖然正確了，但是卻TLE...
準確的做法是動態規劃，艾，今天三題沒有一個是自己想出來的...悲劇...
詳細的狀態轉化方程見代碼注釋
代碼:
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 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1080思路:
想法與最長公共子序列類似
用f[i][j]表示str_a[1..i]與str_b[1..j]的相似度，而所求即f[len_a][len_b]，需要注意初始化部分的代碼
狀態轉移方程見代碼注釋
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 101
5 #define INF 'I'
6 #define Score(ch_a, ch_b) (score[map[ch_a-'A']][map[ch_b-'A']])
7 int len_a, len_b;
8 char str_a[MAX_LEN+1], str_b[MAX_LEN+1];
9 int table[MAX_LEN][MAX_LEN];
10 const int score[][5] = {{5,-1,-2,-1,-3}, {-1,5,-3,-2,-4}, {-2,-3,5,-2,-2}, {-1,-2,-2,5,-1}, {-3,-4,-2,-1,-65535}};
11 /* A C G I T */
12 const int map[] = {0,-1,1,-1,-1,-1,2,-1,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3};
13
14 /*
15 * f[i][j] represent the similarity of str_a[1..i] and str_b[1..j], so:
16 * f[i][j] = max { f[i-1][j-1]+Score(str_a[i], str_b[j]),
17 * f[i-1][j] + Score(str_a[i], '-'),
18 * f[i][j-1] + Score('-', str_b[j]) }
19 */
20 int
21 dp()
22 {
23 int i, j, a, b, c, max;
24 /* Attention: Initialization */
25 table[0][0] = 0;
26 for(i=1; i<=len_a; i++)
27 table[i][0] = table[i-1][0] + Score(str_a[i], INF);
28 for(j=1; j<=len_b; j++)
29 table[0][j] = table[0][j-1] + Score(str_b[j], INF);
30
31 for(i=1; i<=len_a; i++) {
32 for(j=1; j<=len_b; j++) {
33 a = table[i-1][j-1] + Score(str_a[i], str_b[j]);
34 b = table[i-1][j] + Score(str_a[i], INF);
35 c = table[i][j-1] + Score(INF, str_b[j]);
36 max = a > b ? a : b;
37 max = c > max ? c : max;
38 table[i][j] = max;
39 }
40 }
41 return table[len_a][len_b];
42 }
43
44 int
45 main(int argc, char **argv)
46 {
47 int tests;
48 scanf("%d", &tests);
49 while(tests--) {
50 scanf("%d %s", &len_a, str_a+1);
51 scanf("%d %s", &len_b, str_b+1);
52 printf("%d\n", dp());
53 }
54 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1160思路:
事先知道這是動態規劃的題，于是就拼命往這方面想，想啊想啊想啊想，終于靈感一現:
可以用f[i][j]表示到第i個村鎮為止，建造j個郵局所需要的最小距離
心中竊喜，感覺應該挺靠譜，于是繼續深入，直覺告訴我f[i][j]與f[i-1][j], f[i-1][j-1]應該有關系，貌似成了第i個村鎮建不建郵局的子問題，繼續苦思冥想，結果卻還是想不出來。
無奈，還是看別人的思路吧:
用f[i][j]表示前i個郵局建在前j個村鎮所需要的最小距離(貌似，跟我之前想的剛好相反)
f[i][j] = min( f[i-1][k] + cost[k+1][j], i-1<=k<=j-1)，cost[i][j]表示在村鎮i與j之間建造一個post office的最小距離(人家說顯然在中點)
艾，差之毫厘，謬以千里，如何有效地表示和分析最優子結構是關鍵：一個問題的解，如何通過其子問題來表示和求解
代碼:
1 /* 752K 79MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_V 301
6 #define MAX_P 31
7 #define INF 0x7FFFFFFF
8 int v, p;
9 int pos[MAX_V];
10 int cost[MAX_V][MAX_V];
11 int table[MAX_P][MAX_V];
12
13 void
14 init()
15 {
16 int i, j, k, mid, diff;
17 for(i=1; i<=v; i++) {
18 for(j=i; j<=v; j++) {
19 diff = 0;
20 mid = (i+j)/2;
21 for(k=i; k<=j; k++)
22 diff += ((pos[k]>pos[mid])?(pos[k]-pos[mid]):(pos[mid]-pos[k]));
23 cost[i][j] = cost[j][i] = diff;
24 }
25 }
26 }
27
28 int
29 dp()
30 {
31 int i, j, k, min, tmp;
32 memset(table, 0, sizeof(table));
33 for(j=1; j<=v; j++)
34 table[1][j] = cost[1][j];
35 for(i=2; i<=p; i++) {
36 for(j=i+1; j<=v; j++) {
37 min = INF;
38 for(k=i-1; k<=j-1; k++) {
39 tmp = table[i-1][k] + cost[k+1][j];
40 min = tmp<min ? tmp : min;
41 }
42 table[i][j] = min;
43 }
44 }
45 return table[p][v];
46 }
47
48 int
49 main(int argc, char **argv)
50 {
51 int i;
52 while(scanf("%d %d", &v, &p)!=EOF) {
53 for(i=1; i<=v; i++)
54 scanf("%d", pos+i);
55 init();
56 printf("%d\n", dp());
57 }
58 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1159思路:
看完題目，完全不知道該怎么做
參考discuss，發現原來DP這么這么地強大，自己那是相當菜
設ch[1]..ch[n]表示字符串1至n位，i為左游標，j為右游標 ，則i從n遞減，j從i開始遞增。
min[i][j]表示i和j之間至少需要插入多少個字符才能對稱,初始置全0 ,我們最終需要得到的值是min[1][n].
則
if(ch[i]==ch[j]) //如果兩個游標所指字符相同，向中間縮小范圍
min[i][j]=min[i+1][j-1];
else
min[i][j] = 1 +（min[i+1][j]和min[i][j-1]中的較小值）; //如果不同，典型的狀態轉換方程額，狀態方程看明白了，結果發現代碼居然不知道怎么寫...那個汗哪...
原因是沒有發現當i>j時，min[i][j] = 0
代碼(記憶化搜索):
1 /* Time: 1594MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 5001
6 char str[MAX_LEN+1];
7 int len;
8 short memory[MAX_LEN][MAX_LEN];
9
10 /*
11 * f[i][j] represent the minimal insert for str[i..j]
12 *
13 * f[i][j] = f[i+1][j-1], if str[i]==str[j], otherwise
14 * f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
15 */
16 int
17 func(int i, int j)
18 {
19 int a, b;
20 if(i >= j)
21 return 0;
22 if(memory[i][j])
23 return memory[i][j];
24 if(str[i] == str[j])
25 memory[i][j] = func(i+1, j-1);
26 else {
27 a = func(i+1, j);
28 b = func(i, j-1);
29 memory[i][j] = a<b ? a+1 : b+1;
30 }
31 return memory[i][j];
32 }
33
34 int
35 main(int argc, char **argv)
36 {
37 while(scanf("%d", &len) != EOF) {
38 memset(memory, 0, sizeof(memory));
39 scanf("%s", str+1);
40 printf("%d\n", func(1, len));
41 }
42 }
代碼(dp):
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 5001
5 char str[MAX_LEN];
6 int len;
7 short table[MAX_LEN][MAX_LEN];
8
9 short
10 dp()
11 {
12 int i, j;
13 /* if i>j, then table[i][j] = 0 */
14 for(i=len-1; i>=1; i--) {
15 for(j=i; j<=len; j++) {
16 if(str[i] == str[j])
17 table[i][j] = table[i+1][j-1];
18 else
19 table[i][j] = table[i+1][j]<table[i][j-1] ? table[i+1][j]+1 : table[i][j-1]+1;
20 }
21 }
22 return table[1][len];
23 }
24
25 int
26 main(int argc, char **argv)
27 {
28 while(scanf("%d", &len) != EOF) {
29 memset(table, 0, sizeof(table));
30 scanf("%s", str+1);
31 printf("%d\n", dp());
32 }
33 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2250思路:
以單詞為單位的LCS，另外需要記錄路徑信息
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_NUM 101
5 #define MAX_LEN 31
6 char first[MAX_NUM][MAX_LEN];
7 char second[MAX_NUM][MAX_LEN];
8 int fcnt, scnt;
9 int table[MAX_NUM][MAX_NUM];
10 char path[MAX_NUM][MAX_NUM];
11
12 void
13 output(int i, int j)
14 {
15 if(i==0 || j==0)
16 return;
17 if(path[i][j] == 'u')
18 output(i-1, j);
19 else if(path[i][j] == 'l')
20 output(i, j-1);
21 else {
22 output(i-1, j-1);
23 printf("%s ", first[i-1]);
24 }
25 }
26
27 void
28 lcs()
29 {
30 int i, j;
31 for(i=0; i<=fcnt; i++)
32 table[i][0] = 0;
33 for(j=0; j<=scnt; j++)
34 table[0][j] = 0;
35 for(i=1; i<=fcnt; i++) {
36 for(j=1; j<=scnt; j++) {
37 if(strcmp(first[i-1], second[j-1]) == 0) {
38 table[i][j] = table[i-1][j-1] + 1;
39 path[i][j] = 'y';
40 } else if(table[i-1][j] > table[i][j-1]) {
41 table[i][j] = table[i-1][j];
42 path[i][j] = 'u';
43 } else {
44 table[i][j] = table[i][j-1];
45 path[i][j] = 'l';
46 }
47 }
48 }
49 }
50
51 int
52 main(int argc, char **argv)
53 {
54 while(1) {
55 fcnt = scnt = 0;
56 memset(table, 0, sizeof(table));
57 memset(path, 0, sizeof(path));
58 if(scanf("%s", first[fcnt++]) == EOF)
59 break;
60 while(scanf("%s", first[fcnt]) && first[fcnt][0]!='#')
61 ++fcnt;
62 while(scanf("%s", second[scnt]) && second[scnt][0]!='#')
63 ++scnt;
64 lcs();
65 output(fcnt, scnt);
66 printf("\n");
67 }
68 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1953思路:
如果想通了，其實就是道挺簡單的動規題
zero_end[i]記錄第i位以0結尾的合法排列
one_end[i]記錄第i位以1結尾的合法排列
狀態方程即:
zero_end[i+1] = zero_end[i] + one_end[i]
one_end[i+1] = zero_end[i]
以深度搜索的遞歸樹即可觀察得出以上結論(*^__^*) 嘻嘻……
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 45
5 int zero_end[MAX_LEN+1];
6 int one_end[MAX_LEN+1];
7
8 int
9 build_table()
10 {
11 int i;
12 zero_end[1] = 1;
13 one_end[1] = 1;
14 for(i=2; i<=45; i++) {
15 zero_end[i] = zero_end[i-1] + one_end[i-1];
16 one_end[i] = zero_end[i-1];
17 }
18 }
19
20 int
21 main(int argc, char **argv)
22 {
23 int i, n, tests;
24 build_table();
25 scanf("%d", &tests);
26 for(i=1; i<=tests; i++) {
27 scanf("%d", &n);
28 printf("Scenario #%d:\n%d\n\n", i, zero_end[n]+one_end[n]);
29 }
30 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1163思路:
比較基礎、容易的動態規劃
table[i][j]記錄從根節點到第i行第j個元素的最大和
狀態轉移方程:
table[i][j] = max(table[i][j-1], table[i][j]) + num[i][j]
為了節省空間，對于三角形的保存，采用了一維數組
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 101
5 #define MAX_LEN 5051 /* 1+2+3+
+100 */
6 int rows, num[MAX_LEN];
7 int table[MAX_N][MAX_N];
8
9 /* table[i][j] = max(table[i-1][j-1]+num[i][j], table[i-1][j]+num[i][j] */
10 int
11 dp()
12 {
13 int i, j, k, tmp, max, rt;
14 table[0][0] = num[0];
15 for(i=1; i<rows; i++) {
16 tmp = i*(i+1)/2;
17 for(j=0; j<=i; j++) {
18 max = 0;
19 for(k=1; k>=0; k--)
20 if(j-k>=0 && j-k<=i-1) /* parent index: [i-1][j-k] */
21 max = table[i-1][j-k]+num[tmp+j]>max ? table[i-1][j-k]+num[tmp+j] : max;
22 table[i][j] = max;
23 }
24 }
25 rt = 0;
26 for(j=0; j<rows; j++)
27 if(table[rows-1][j] > rt)
28 rt = table[rows-1][j];
29 return rt;
30 }
31
32 int
33 main(int argc, char **argv)
34 {
35 int i, j, tmp;
36 while(scanf("%d", &rows) != EOF) {
37 for(i=0; i<rows; i++) {
38 tmp = i*(i+1)/2;
39 for(j=0; j<=i; j++)
40 scanf("%d", num+(tmp+j));
41 }
42 memset(table, 0, sizeof(table));
43 printf("%d\n", dp());
44 }
45 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1276思路:
典型的多重背包問題，參考背包九講，一次AC
深刻理解：01背包、完全背包、多重背包
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_VOLUMN 100001
5 #define MAX_N 11
6 #define max(a,b) ((a)>(b) ? (a) : (b))
7 int vol, n;
8 int cv[MAX_N], num[MAX_N], f[MAX_VOLUMN];
9
10 /* f[i][v] = max(f[i-1][v], f[i-1][v-cost[i]]+value[i]) */
11 void
12 ZeroOnePack(int cost, int value)
13 {
14 int v;
15 for(v=vol; v>=cost; v--)
16 f[v] = max(f[v], f[v-cost]+value);
17 }
18
19 /* f[i][v] = max(f[i-1][v], f[i][v-cost[i]]+value[i]) */
20 void
21 CompletePack(int cost, int value)
22 {
23 int v;
24 for(v=cost; v<=vol; v++)
25 f[v] = max(f[v], f[v-cost]+value);
26 }
27
28 void
29 MultiplePack(int cost, int value, int amount)
30 {
31 int k = 1;
32 if(cost*amount >= vol)
33 CompletePack(cost, value);
34 else {
35 while((amount-k) >= 0) {
36 ZeroOnePack(cost*k, value*k);
37 amount -= k;
38 k = k*2;
39 }
40 ZeroOnePack(cost*amount, value*amount);
41 }
42 }
43
44 void
45 dp()
46 {
47 int i;
48 for(i=1; i<=n; i++)
49 MultiplePack(cv[i], cv[i], num[i]);
50 }
51
52 int
53 main(int argc, char **argv)
54 {
55 int i;
56 while(scanf("%d %d", &vol, &n)!=EOF) {
57 memset(f, 0, sizeof(f));
58 for(i=1; i<=n; i++)
59 scanf("%d %d", num+i, cv+i);
60 dp();
61 printf("%d\n", f[vol]);
62 }
63 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3624思路:
典型的01背包問題，動態規劃，參考背包九講
注意需要使用滾動數組，否則MLE
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 3403
5 #define MAX_M 12881
6 #define max(a,b) ((a)>(b) ? (a) : (b))
7 int n, m;
8 /* MLE: int table[MAX_N][MAX_M]; */
9 int table[MAX_M];
10 int weight[MAX_N], rate[MAX_N];
11
12 void
13 dp()
14 {
15 int i, j;
16 memset(table, 0, sizeof(table));
17 for(i=1; i<=n; i++)
18 for(j=m; j>=weight[i]; j--) /* Attention: descent order */
19 table[j] = max(table[j], table[j-weight[i]]+rate[i]);
20 }
21
22 int
23 main(int argc, char **argv)
24 {
25 int i;
26 while(scanf("%d %d", &n, &m)!=EOF) {
27 for(i=1; i<=n; i++)
28 scanf("%d %d", weight+i, rate+i);
29 dp();
30 printf("%d\n", table[m]);
31 }
32 }