poj 1088滑雪问题

#include<iostream>using namespace std;const int Max = 105;int row, col;int map[Max][Max]; // 记录图各点的高度。int dp[Max][Max]; // 记录以各点为起点的最长下降路径的长度。int dfs(int r, int c){ if(dp[r][c] != 0) return dp[r][c]; // 若dp[r][c]不为0，则表示它已被访问。 int max = 1; if(r + 1 <= row && map[r][c] > map[r + 1][c]){ int len = dfs(r + 1, c) + 1; if(len > max) max = len; } if(r - 1 >= 1 && map[r][c] > map[r - 1][c]){ int len = dfs(r - 1, c) + 1; if(len > max) max = len; } if(c + 1 <= col && map[r][c] > map[r][c + 1]){ int len = dfs(r, c + 1) + 1; if(len > max) max = len; } if(c - 1 >= 1 && map[r][c] > map[r][c - 1]){ int len = dfs(r, c - 1) + 1; if(len > max) max = len; } return map[r][c] = max; }int main(){ int i, j; cin >> row >> col; for(i = 1; i <= row; i ++) for(j = 1; j <= col; j ++) cin >> map[i][j];int ans = 0;memset(dp, 0, sizeof(dp));for(i = 1; i <= row; i ++)for(j = 1; j <= col; j ++){dp[i][j] = dfs(i, j); // 用记忆化搜索求出dp[i][j]，同时也求出了其路径上的dp[x][y]。if(dp[i][j] > ans)ans = dp[i][j];}cout << ans << endl;return 0;}

?