蒟蒻求助，dp

zhangxiao666 @ 2023-01-09 23:02:06

#include<bits/stdc++.h>
using namespace std;
int r,c,cnt,ans=1;
struct stu{
    int x,y;
    int h;
}a[10010];
int dp[10010];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool cmp(stu a1,stu a2){
    return a1.h>a2.h;
}
bool check(int i,int j){
    for(int k=0;k<4;k++){
        if(a[i].x+dx[k]==a[j].x&&a[i].y+dy[k]==a[j].y) return true;
    }
    return false;
} 
int main(){
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            scanf("%d",&a[++cnt].h);
            a[cnt].x=i;
            a[cnt].y=j;
        }
    }
    sort(a+1,a+cnt+1,cmp);
    dp[1]=1;
    for(int i=2;i<=cnt;i++){
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(check(i,j)){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

by wangqz @ 2023-01-09 23:23:25

@zhangxiao666 天啊，我写的居然是dfs

by wangqz @ 2023-01-09 23:24:46

还没有记忆化

by zhangxiao666 @ 2023-01-10 15:42:14

@wangqz 不写记忆化能过？太牛了

by dugujiujian @ 2023-01-28 19:13:49

同学你好我看不太出你代码的问题 但我借助你的思路用dp的方式写了这道题 你可以简单的看一下 我觉得我们主要的不同就在于我特地拿了一个二维数组来保留输入的数组情况（我的代码应该是有很多的优化空间的，我写的比较粗糙）

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};
int shuru[110][110];//存储输入 
int dp[110][110];//记录当前点最大的递减长度 
class node{//记录每个点的 3个元素 坐标（x，y）以及高度 
    public:
        int x;int y;int h;
}a[110*110];//数组 
bool Com(node n1,node n2)//自定义排序 按照高度从小到达排序 
{
    return n1.h<n2.h;
}
int main()
{
    int res=0;
    cin>>n>>m;
    int k=0;//让a[]数组自己走 
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)//读入输入 
    {
        a[k].x=i;a[k].y=j;//记录当前点的位置 
        cin>>a[k].h;//同时记录高度 利于之后的排序 
        shuru[i][j]=a[k].h;//这个shuru数组是用来与a[k].h对比的高度的 
        k++;//数组自动后移动 
    }
    sort(a,a+n*m,Com);//将点位按照从小到大的高度排序
//  for(int i=1;i<=n*m;i++)//验证dp情况 
//  {
//      cout<<a[i-1].h<<" ";
//      if(i%n==0)
//      cout<<endl;
//  }
//  
    for(int i=0;i<n*m;i++)
    {//从a[]数组的第一个开始逐个记录dp情况 
    //也就是从高度最矮的坐标开始访问 
        for(int j=0;j<4;j++)//看周边的四个点 
        {
            int f=dx[j]+a[i].x,s=dy[j]+a[i].y;
            // f , s 分别表示 周边四个点的 x , y
            if(f>=0&&f<n&&s>=0&&s<m&&a[i].h>shuru[f][s])
            {
                //dp[a[i].x][a[i].y]就是当前访问点的dp值
                // dp[f][s]就是周边访问点的dp值 
                dp[a[i].x][a[i].y]=max(dp[a[i].x][a[i].y],dp[f][s]+1);
            }
        }
        res=max(res,dp[a[i].x][a[i].y]);
        //每次访问完一个点的dp值就进行比对看是不是最大的 
    }
    cout<<res+1;
}

by dugujiujian @ 2023-01-28 19:16:28

@dugujiujian 这里n*m的意思是输入的二维数组元素的总个数

by zhangxiao666 @ 2023-02-02 18:21:45

@dugujiujian

感谢大神，ntql