A Za, A Za, Fighting...

问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2192

思路:
原本以为是类似于PKU 1936的简单题，结果Sample测试不过，发现对于像cat, tree这样包含相同字母(这里是t)的例子需要回溯，于是DFS，这样结果虽然正确了，但是却TLE...
准确的做法是动态规划，艾，今天三题没有一个是自己想出来的...悲剧...
详细的状态转化方程见代码注释

代码:

问题:
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]，需要注意初始化部分的代码
状态转移方程见代码注释

代码:

问题:
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的最小距离(人家说显然在中点)

艾，差之毫厘，谬以千里，如何有效地表示和分析最优子结构是关键：一个问题的解，如何通过其子问题来表示和求解

代码:

问题:
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，另外需要记录路径信息

代码:

问题:
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]
以深度搜索的递归树即可观察得出以上结论(*^__^*) 嘻嘻……

代码:

问题:
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]

为了节省空间，对于三角形的保存，采用了一维数组

代码:

问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1276

思路:
典型的多重背包问题，参考背包九讲，一次AC
深刻理解：01背包、完全背包、多重背包

代码:

问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3624

思路:
典型的01背包问题，动态规划，参考背包九讲
注意需要使用滚动数组，否则MLE

代码:

     摘要:                                                         ...  阅读全文