| syhd142 |
|
|||
|
日歷
統計
導航常用鏈接留言簿(2)隨筆檔案(23)文章分類(270)
文章檔案(122)我的豆瓣搜索最新評論
|
傳說中經典DP,記憶化搜索?其實就是在一個二維數組中求一個最長下降的子序列的長度。 其實就是從每個元素開始找以它為起始點的最長下降子序列,當遞歸到該點比周圍所有的點都小時即返回, 自低向上的方法,注意與廣搜不同,廣搜是自頂向下。 以后每個點的計算都可以用到以前的結果,因為這是無后效性的?這就是傳說中的記憶化? #include <stdio.h>
#include <string.h> #define N 105 #define INF 1 << 28 int r, c; int h[N][N], a[N][N]; int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int dfs(int x, int y) { if(a[x][y]) return a[x][y]; int max = 0, t; for(int i = 0; i < 4; i++) { int xx = x + dir[i][0]; int yy = y + dir[i][1]; if(xx < 0 || xx >= r || yy < 0 || yy >= c) continue; if(h[xx][yy] < h[x][y]) { t = dfs(xx, yy); max = max > t ? max : t; } } a[x][y] = max + 1; return max + 1; } int main() { int ans; while(~scanf("%d %d", &r, &c)) { for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) { scanf("%d", &h[i][j]); a[i][j] = 0; } ans = -INF; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) { int t = dfs(i, j); if(t > ans) ans = t; } printf("%d\n", ans); } return 0; }
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|
| Copyright © Fucker | Powered by: 博客園 模板提供:滬江博客 |