poj1088 滑雪动态规划+回溯

最新推荐文章于 2022-04-18 12:00:07 发布

完美代码

最新推荐文章于 2022-04-18 12:00:07 发布

阅读量1.1w

点赞数 1

谢绝转载-https://update.blog.csdn.net

本文链接：https://blog.csdn.net/update7/article/details/57414970

版权

编程. 同时被 2 个专栏收录

578 篇文章 ¥299.90 ¥399.90

订阅专栏

编程..

570 篇文章 ¥299.90 ¥399.90

订阅专栏

该博客介绍了如何使用动态规划和回溯法解决POJ1088滑雪问题。通过读取矩阵并设置初始条件，博主逐步展示如何遍历矩阵并找到最长的下降路径，最终输出最长路径的长度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include<iostream>
#include<cstdio>
using namespace std;
int num,n,m,a[1000][1000],d[1000][1000],maxx;
int dp(int i,int j){
if(d[i][j]!=-1) return d[i][j];
if(i-1>=1&&a[i-1][j]<a[i][j])
    d[i][j]=max(d[i][j],dp(i-1,j));
if(i+1<=n&&a[i+1][j]<a[i][j])
    d[i][j]=max(d[i][j],dp(i+1,j));
if(j+1<=m&&a[i][j+1]<a[i][j])
    d[i][j]=max(d[i][j],dp(i,j+1));
if(j-1>0&&a[i][j-1]<a[i][j])
    d[i][j]=max(d[i][j],dp(i,j-1));
    d[i][j]++;
return d[i][j];
}
int main(){
        maxx=-1;
        cin>>n>>m;
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
    cin>>a[i][j];
    d[i][j]=-1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        maxx=max(maxx,dp(i,j));
    cout<<maxx+1<<endl;
}