问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1028思路:
这是道简单题，1次AC呵呵
最简单的做法莫过于直接用两个堆栈根据题目的description进行模拟
不过，这里，我只用了一个数组来模拟所有的动作
需要注意的一点是: FORWARD的动作只有在之前存在BACK动作的条件下才有可能有效
1 #define LEN_MAX 71
2 #define NUM_MAX 100
3 #define CMD_MAX 8
4 #define QUIT "QUIT"
5 #define FORWARD "FORWARD"
6 #define VISIT "VISIT"
7 #define BACK "BACK"
8 #define IGN "Ignored"
9 char cmd[CMD_MAX];
10 char addr[LEN_MAX];
11 char arr[NUM_MAX][LEN_MAX];
12 int cur_pos, bk_pos, fw_pos;
13 int can_fw_count;
14
15 int
16 main(int argc, char **argv)
17 {
18 cur_pos = can_fw_count = 0;
19 bk_pos = fw_pos = -1;
20 strcpy(arr[cur_pos], "http://www.acm.org/");
21 while(scanf("%s", cmd)!=EOF && strcmp(cmd, QUIT)!=0) {
22 if(strcmp(cmd, VISIT)==0) {
23 scanf("%s", addr);
24 strcpy(arr[++cur_pos], addr);
25 bk_pos = cur_pos - 1;
26 can_fw_count = 0;
27 printf("%s\n", arr[cur_pos]);
28 } else if(strcmp(cmd, BACK)==0) {
29 if(bk_pos == -1)
30 printf("%s\n", IGN);
31 else {
32 fw_pos = cur_pos;
33 cur_pos = bk_pos;
34 bk_pos = cur_pos-1;
35 ++can_fw_count;
36 printf("%s\n", arr[cur_pos]);
37 }
38 } else if(strcmp(cmd, FORWARD)==0) {
39 if(fw_pos == -1 || !can_fw_count)
40 printf("%s\n", IGN);
41 else {
42 bk_pos = cur_pos;
43 cur_pos = fw_pos;
44 fw_pos = cur_pos+1;
45 --can_fw_count;
46 printf("%s\n", arr[cur_pos]);
47 }
48 }
49 }
50 return 0;
51 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1015思路:
最小差最大和问题
这题...一点想法都没有，就是不会写，只好上网搜索人家的思路，总结如下
动态规划状态方程:
f(j, k) = f(j-1, x), x+(di-pi) = k
这里，f(j, k)表示选择了j个人，其最小差为k且满足最大和的解
另外，还需要记录已选择了哪些人，因为在状态迁移的过程中，只能选择之前未被选择过的人
1 int base = m*MAX_GRADE; /* 防止出现负数 */
2 memset(f, -1, sizeof(f));
3 memset(sum, -1, sizeof(sum));
4 /* initialize */
5 for(i=1; i<=n; i++)
6 if(sum[1][minus[i]+base] < plus[i]) {
7 f[1][minus[i]+base] = i;
8 sum[1][minus[i]+base] = plus[i];
9 }
10 for(j=2; j<=m; j++) {
11 for(k=0; k<=2*m*MAX_GRADE; k++) {
12 if(f[j-1][k] != -1) {
13 for(i=1; i<=n; i++) {
14 /* see if i has been used */
15 q = k;
16 for(p=j-1; p>=1; p--) {
17 if(f[p][q] == i)
18 break;
19 q -= minus[f[p][q]];
20 }
21 if(p<1) {
22 if(sum[j][k+minus[i]] < sum[j-1][k]+plus[i]) {
23 f[j][k+minus[i]] = i;
24 sum[j][k+minus[i]] = sum[j-1][k]+plus[i];
25 }
26 }
27 }
28 }
29 }
30 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1088思路1:
这题是前段时间微软笔试的最后一道大题，当时没想太多，直接简单DFS，没想到会超时，结果嘛直接被BS了...太菜啊
我们从最优解开始分析:
设p[1]--p[2]--p[3]...--p[n]即为最长的一条路径L, p[i]=(xi, yi)
对于该路径L中的一个点p[i], 可以这样来理解: 到达点p[i]的最长路径是到达点p[i-1]的最长路径加1， 并且height(p[i-1])大于height(p[i])
因此，我们可以
先将输入地图按照高度从高到低排序，然后从头开始依次求出最长路径需要注意的一点：
下面代码的第8行需要设置max为1，而不是0， 因为该点可能是最高点(peek)
1 int
2 dp()
3 {
4 int total = row*col;
5 int i, j, x, y, sx, sy, td, max, longest=1;
6 distance[points[0].x][points[0].y] = 1; //highest point
7 for(i=1; i<total; i++) {
8 max = 1; //max should be set 1, in case points[i] is a peek
9 x = points[i].x;
10 y = points[i].y;
11 for(j=0; j<4; j++) { //four directions
12 sx = x+dx[j];
13 sy = y+dy[j];
14 //points[sx*col+sy] is a higher point around points[i]
15 if(can_go(sx, sy) && points[i].height<height[sx*col+sy]) { //distance[sx][sy]>0 indicates (sx, sy) a higher point
16 td = distance[sx][sy]+1;
17 max = max > td ? max : td;
18 }
19 }
20 distance[x][y] = max;
21 longest = longest > max ? longest : max;
22 }
23 return longest;
24 }
思路2:
备忘录方法
这里我们换一种看待该问题的方式
该题有一个很自然的想法，那就是依次枚举每个点，计算从每个点出发的最长路径，最后求这些最长路径的最大值即可
从一个点p[i]出发的最长路径是: 从其上下左右四个点出发的最长路径的最大值加1
备忘录方法真的非常好用，而且理解起来也较动态规划简单呵呵，原本超时的代码只要稍加修改就可以AC了
1 int
2 dp_memory(int x, int y)
3 {
4 if(opt[x][y] != 0) //memory, simple but powerful
5 return opt[x][y];
6
7 int max = 0;
8 int i, sx, sy, tmp;
9 for(i=0; i<4; i++) { // four directions
10 sx = x + dx[i];
11 sy = y + dy[i];
12 if(sx>=0 && sx<=row-1 && sy>=0 && sy<=col-1 && map[sx][sy]<map[x][y]) {
13 tmp = dp_memory(sx, sy);
14 max = max > tmp ? max : tmp;
15 }
16 }
17 opt[x][y] = max+1;
18 return opt[x][y];
19 }
1 for(i=0; i<row; i++)
2 for(j=0; j<col; j++) {
3 tmp = dp_memory(i, j);
4 max = max > tmp ? max : tmp;
5 }
6
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1579思路:
根据题意的描述，采用递归是显然易见的
不过，该题的另一个突出的特点是重复子问题，如何既可以获得递归的简洁，又同时可以避免重复子问题的多次计算呢？
这时，就可以采用
备忘录方法 1 #define MAX 21
2 long table[MAX][MAX][MAX];
3
4 long
5 function_run_fun(int a, int b, int c)
6 {
7 if(a<=0 || b<=0 || c<=0)
8 return 1;
9 if(a>20 || b>20 || c>20)
10 return (table[20][20][20] = function_run_fun(20, 20, 20));
11
12 if(table[a][b][c] != 0) //memory search
13 return table[a][b][c];
14
15 else if(a<b && b<c)
16 table[a][b][c] = function_run_fun(a, b, c-1) + function_run_fun(a, b-1, c-1) - function_run_fun(a, b-1, c);
17 else
18 table[a][b][c] = function_run_fun(a-1, b, c) + function_run_fun(a-1, b-1, c) + function_run_fun(a-1, b, c-1) - function_run_fun(a-1, b-1, c-1);
19 return table[a][b][c];
20 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3356思路:
与最长公共子序列挺相似的一道动态规划
if(first[i] == second[j])
f(i, j) = min(f(i-1, j-1)[nothing], f(i-1, j)+1[deletion], f(i, j-1)+1[insertion])
else
f(i, j) = min(f(i-1, j-1)+1[change], f
(i-1, j)+1[deletion], f(i, j-1)+1[insertion])
其中，f(i, j)表示使first[0..i]转化成second[0..j]所需要的最小操作数
一个需要注意的问题是table的初始化，一开始想当然地将table[i][0], table[0][j]初始化为无穷大，导致出错
这可以说是一个普遍化的问题，就是要
注意动态规划时的初始化 1 int
2 dfs()
3 {
4 int i, j;
5 /* Attention: initialize */
6 /* set table[i][0] and table[0][j] to INT_MAX, which caused WA */
7 for(i=0; i<=m; i++)
8 table[i][0] = i;
9 for(j=0; j<=n; j++)
10 table[0][j] = j;
11 for(i=1; i<=m; i++) {
12 for(j=1; j<=n; j++) {
13 if(x[i-1] == y[j-1])
14 table[i][j] = min(table[i-1][j-1], table[i-1][j]+1, table[i][j-1]+1);
15 else
16 table[i][j] = min(table[i-1][j-1], table[i-1][j], table[i][j-1]) + 1;
17 }
18 }
19 return table[m][n];
20 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1458思路:
额...最长公共子序列(LCS), 经典动态规划(详情见CLRS)
if(first[i] == second[j])
f(i, j) = f(i-1, j-1) + 1
else
f(i, j) = max(f(i-1, j), f(i, j-1))
1 int
2 dp_lcs()
3 {
4 int i, j;
5 for(i=0; i<=m; i++)
6 table[i][0] = 0;
7 for(j=0; j<=n; j++)
8 table[0][j] = 0;
9
10 for(i=1; i<=m; i++) {
11 for(j=1; j<=n; j++) {
12 if(fst[i-1] == snd[j-1])
13 table[i][j] = table[i-1][j-1] + 1;
14 else
15 table[i][j] = max(table[i-1][j], table[i][j-1]);
16 }
17 }
18 return table[m][n];
19 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2479http://acm.pku.edu.cn/JudgeOnline/problem?id=2593http://acm.pku.edu.cn/JudgeOnline/problem?id=1050思路:
基础: 最大子段和问题
给定N个整数(可能为负)组成的序列a1, a2, a3, ..., aN，求子段ai, a(i+1), ... , aj的和的最大值
非常典型的动态规划，状态迁移方程:
f(i) = max(ai, f[i-1]+ai), f(i)表示以ai结尾的最大子段和据此我们可以得到O(n)的求解算法
PKU 2479与2593这两题其实是同一个问题(
买一送一)，都是上述最大子段和问题的变形
一样非常自然的想法是枚举所有可能的"分开点", 然后分别计算前后两个子数组的最大子段和，不过如果依次枚举的话是会超时的
这时候就需要利用对于上述f(i)表达式的理解了, 我们可以依次从头到尾、从尾到头扫描两次原数组，并把相应的最大子段和分别保存起来，称为hd[i]和tl[i], 这里注意f(i)并非是最大子段和
假设现在枚举到分开点t, 那么a[0..t]的最大子段和可以通过hd[i]获得，a[t+1...len]的最大子段和则可以通过tl[i]获得
1 /*
2 * hd[i] stores the maximum sub-segment from arr[0..i]
3 * tl[i] stores the maximum sub_segment from arr[i+1..n-1]
4 */
5 long *hd, *tl;
6
7 long
8 max_subsum(int *arr, long N)
9 {
10 long i, temp, max;
11 /* hd */
12 hd[0] = max = arr[0];
13 for(i=1; i<N; i++) {
14 temp = hd[i-1] + arr[i];
15 hd[i] = temp>arr[i] ? temp : arr[i];
16 }
17 for(i=1; i<N; i++) {
18 hd[i] = hd[i] > max ? hd[i] : max;
19 max = hd[i];
20 }
21 /* tl */
22 tl[N-1] = max = arr[N-1];
23 for(i=N-2; i>=0; i--) {
24 temp = tl[i+1] + arr[i];
25 tl[i] = temp>arr[i] ? temp : arr[i];
26 }
27 for(i=N-2; i>=0; i--) {
28 tl[i] = tl[i] > max ? tl[i] : max;
29 max = tl[i];
30 }
31 }
32
33 long
34 enumerate()
35 {
36 long i, temp, max = hd[0] + tl[1];
37 for(i=1; i<n-1; i++) {
38 temp = hd[i] + tl[i+1];
39 max = max>temp ? max : temp;
40 }
41 return max;
42 }
PKU 1050是一道"隐藏"地比较深的最大子段和问题，之所以说它隐藏的比较深，是因为题目要求的是求最大子矩阵问题
上网搜了别人的思路，才发现这题是可以转化成求最大子段和问题的：只要将矩阵的行或者列合并即可
不得不感叹这思路的精妙啊呵呵
1 int
2 max_subsum(int *arr, int N)
3 {
4 int i, t, max;
5 max = t = arr[0];
6 for(i=1; i<N; i++) {
7 t = t+arr[i]>arr[i] ? t+arr[i] : arr[i];
8 max = max>t ? max : t;
9 }
10 return max;
11 }
12
13 int
14 enumerate()
15 {
16 int t, max = 0;
17 int i, j, k, len, temp[col];
18 memset(temp, 0, sizeof(int)*col);
19 for(len=1; len<=row; len++) {
20 for(i=0; i<row; i++) {
21 for(j=i; j<len; j++) {
22 for(k=0; k<col; k++) {
23 temp[k] += arr[j][k];
24 }
25 }
26 t = max_subsum(temp, col);
27 max = max>t ? max : t;
28 memset(temp, 0, sizeof(int)*col);
29 }
30 }
31 return max;
32 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1014思路:
1. 深度搜索
看到该题的第一个想法就是DFS，很快就写出了代码:
1 void
2 dfs(int *values, int index, long cur_value_sum)
3 {
4 if(cur_value_sum >= value_half) {
5 if(cur_value_sum == value_half)
6 flag = 1;
7 return;
8 }
9 if(index < 1)
10 return;
11 int i;
12 for(i=values[index]; i>=0 && (!flag); i--) {
13 cur_value_sum += (i*index);
14 dfs(values, index-1, cur_value_sum);
15 cur_value_sum -= (i*index);
16 }
17 }
额...结果TLE...
仔细看题，发现maximum total number will be 20000, 所以超时几乎是肯定的
其实，discuss里有人用DFS+Cut通过的，只是自己太菜，还不会减枝
2. 动态规划
2.1 from: http://www.cppblog.com/AClayton/archive/2007/09/14/32185.html声明数组can_reach[60005]
can_reach[i]=1, 表示存在一个人获得价值为 i ,另一个人获得价值为value_sum-i的方案
我们的目标就是要确定can_reach[value_sum>>1]是否等于1
1 int
2 dp()
3 {
4 int i, j, k, temp, cur_max = 0;
5 can_reach[0] = 1;
6 for(i=1; i<=VALUE_MAX; i++) {
7 if(num[i] > 0) {
8 for(j=cur_max; j>=0; j--) { /* tricky, pay attention */
9 if(can_reach[j]) {
10 for(k=1; k<=num[i]; k++) {
11 temp = i*k+j;
12 if(temp == value_half)
13 return 1;
14 if(temp>value_half) /* initial: if(temp>value_half || can_reach[temp]) break; */
15 break;
16 can_reach[temp] = 1;
17 }
18 }
19 }
20 }
21 cur_max += (i*num[i]);
22 if(cur_max>value_half)
23 cur_max = value_half;
24 }
25 }
注意: 上述代码的第14行，原文中存在减枝，但没有看懂，所以没有放进去，还好，该代码还是AC了
2.2 from:
http://blog.sina.com.cn/s/blog_5c95cb070100cvt8.html该问题可以转化成一个0-1背包模型(见：背包九讲)
关键是下面的数论知识:
对于任意一个正整数 n, 它可以表示成:
n = 1 + 1<<1 + 1<<2 + ... + 1<<k + res[余数]
我们可以得到：对于1<=i<=n的任意正整数 i, 它肯定可以表示成: 1, 1<<1, 1<<2, ... 1<<k, res的一个组合
因此，对于该题，我们可以对输入做预处理:
1 len = 0;
2 memset(value_weight, 0, sizeof(value_weight));
3 for(i=1; i<=VALUE; i++) {
4 if(num[i] != 0) {
5 j = 0;
6 while((1<<(j+1)) <= (num[i]+1)) {
7 value_weight[len++] = i*(1<<j);
8 ++j;
9 }
10 if((num[i]+1-(1<<j))>0)
11 value_weight[len++] = i*(num[i]+1-(1<<j));
12 }
13 }
接下来，原问题就转化成:
背包容量value_half(value_sum/2)，每件物品的cost与value都是value_weight[i]，考虑是否存在一种方案，使得总价值等于value_half
0-1背包的典型DP状态方程:
f[i][j] = max(f[i-1][j], f[i-1][j-c[i]]+v[i]), f[i][j]表示前i件物品放入容量为j的背包而可以获得的最大价值
1 int
2 knapsack()
3 {
4 int i, w, pre, cur;
5 memset(table, 0, sizeof(table));
6 for(w=value_weight[0]; w<=value_half; w++) {
7 table[0][w] = value_weight[0];
8 if(table[0][w] == value_half)
9 return 1;
10 }
11 for(i=1; i<len; i++) {
12 cur = i%2;
13 pre = (i+1)%2;
14 for(w=0; w<=value_half; w++) {
15 if(w>=value_weight[i])
16 table[cur][w] = max(table[pre][w], table[pre][w-value_weight[i]]+value_weight[i]);
17 else
18 table[cur][w] = table[pre][w];
19 if(table[cur][w] == value_half)
20 return 1;
21 }
22 }
23 return 0;
24 }
AC [ Memory: 836K, Time: 16MS]
算法，始终是自己最为薄弱的环节。
距离正式开始找实习、找工作还有一年的时间，好好加油。
坚信：勤能补拙
训练方式：PKU
目标：不求达到ACM的程度(这个...当然可能性也不大(*^__^*) 嘻嘻……), 但求熟练掌握基础
代码:
# Non-members may check out a read-only working copy anonymously over HTTP.
svn checkout http://code-pearl.googlecode.com/svn/trunk/ code-pearl-read-only