|Tyvj|动态规划|P1004 滑雪

http://tyvj.cn/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; }

转载于:https://www.cnblogs.com/flyinthesky1/p/6384354.html

总结

以上是生活随笔为你收集整理的|Tyvj|动态规划|P1004 滑雪的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。