很早就看了这个题,想了很久一直没有实现,后来看别人的代码,说是经典的动态规划,但是我还是看不懂。过了一段时间又自己想了很久,才写成了代码,代码有3000B,在北大运行时间也是200+MS,后来又看了一遍别人的动态规划代码,终于明白怎么规了,然后自己根据别人的代码又重新写了一个动态规划的代码,代码如下,运行时间0MS。(哎....还是动态规划的意思比较明确啊..)
/**规划思想:DP[i][j] = Max{ DP[i-1][j], DP[i+1][j], DP[i][j-1], DP[i][j+1] } + 1;**/ #include <stdio.h> int r, c, map[101][101], dp[101][101], MAX; int DP(int x, int y) { int i, x0, y0, max=0, dir[4][2]={1,0,-1,0,0,1,0,-1}; if (dp[x][y]) return dp[x][y]; for (i=0; i<4; i++) { x0 = x + dir[i][0]; y0 = y + dir[i][1]; if (x0<0 || y0<0 || x0>=r || y0>=c) continue; if (map[x0][y0]<map[x][y] && DP(x0, y0)>max) max = dp[x0][y0]; } dp[x][y] = max + 1; return dp[x][y]; } int main() { int i, j; scanf("%d %d", &r, &c); for (i=0; i<r; i++) for (j=0; j<c; j++) scanf("%d", &map[i][j]); for (i=0; i<r; i++) for (j=0; j<c; j++) { DP(i, j); if (dp[i][j] > MAX) MAX = dp[i][j]; } printf("%d/n", MAX); }