|Tyvj|动态规划|P1004 滑雪

/p/1004

由于考虑高度问题，确保每个值都算出来，这里用的是记忆化搜索。

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int dx[4] = {1,0,-1,0};const int dy[4] = {0,1,0,-1};const int maxrc = 100 + 5;int r,c;int map[maxrc][maxrc];int f[maxrc][maxrc];//设f[i][j]为到达[i,j]时最优值//f[i][j] = max{f[i+a][i+b] | a和b是4个坐标增量，map[i][j]<map[i+a][i+b]}int dfs (int x, int y){if (f[x][y]!=0) return f[x][y];//算过int maxt = 1;int t;for (int i=0;i<4;i++){int tx = x + dx[i], ty = y + dy[i];if (tx>0&&ty>0&&tx<=r&&ty<=c&&map[tx][ty]>map[x][y]){t = dfs(tx,ty)+1;maxt = max(t, maxt);}}f[x][y] = maxt;return maxt;}int main () {scanf("%d%d", &r, &c);for (int i=1;i<=r;i++)for (int j=1;j<=c;j++)scanf("%d", &map[i][j]); memset(f, 0, sizeof(f));int ans = 0;for (int i=1;i<=r;i++)for (int j=1;j<=c;j++){f[i][j] = dfs(i,j);ans = max(ans, f[i][j]);}printf("%d\n", ans);return 0;}