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