POJ 1088 滑雪（动态规划+记忆化搜索）

//动态规划 + 记忆化搜索#include <cstdio>#include <cstring>const int nMax = 107;int R, C;int map[nMax][nMax];int dp[nMax][nMax];int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};int fdp(int x, int y){if(dp[x][y] != 0) return dp[x][y];int k;for(k = 0; k < 4; ++ k){int xx = x + dir[k][0];int yy = y + dir[k][1];if(xx >= 0 && xx < R && yy >= 0 && yy < C && map[xx][yy] < map[x][y]){if(dp[x][y] < fdp(xx, yy) + 1){dp[x][y] = fdp(xx, yy) + 1;}}}if(dp[x][y] == 0) dp[x][y] = 1;return dp[x][y];}int main(){while(scanf("%d%d", &R, &C) != EOF){int i, j;int _min = 0x7fffffff;int x, y;for(i = 0; i < R; ++ i){for(j = 0; j < C; ++ j){scanf("%d", &map[i][j]);if(map[i][j] < _min){_min = map[i][j];x = i;y = j;}}}memset(dp, 0, sizeof(dp));dp[x][y] = 1;for(i = 0; i < R; ++ i)for(j = 0; j < C; ++ j) fdp(i, j);int _max = 0;for(i = 0; i < R; ++ i)for(j = 0; j < C; ++ j) if(dp[i][j] > _max)_max = dp[i][j];printf("%d\n", _max);}return 0;}