問題:
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.shnenglu.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