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 滑雪的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。