用记忆化搜索，80分求调

chenhouye @ 2024-10-07 19:47:07

using namespace std;
int n,m,a[110][110],b[110][110],maxx=0;
int dp(int x,int y){
    if(b[x][y]!=0) return b[x][y];
    if(x<1||x>n||y<1||y>m) return 0;
    int mmm=1;
    for(int i=-1;i<=1;i++){
        for(int j=-1;j<=1;j++){
            int nx=x+i,ny=y+j;
            if((nx==x&&ny==y)||(a[nx][ny]>=a[x][y])) continue;
            mmm=max(mmm,dp(nx,ny)+1);
        }
    }
    b[x][y]=mmm;
    return mmm;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            maxx=max(maxx,dp(i,j));
        }
    }
    printf("%d",maxx);
    return 0;
}

by Jason_Teng @ 2024-10-07 19:51:36

@chenhouye 废话不说，贴代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,a[201][201],s[201][201],ans;
int dfs(int x,int y){
    if(s[x][y])return s[x][y];
    s[x][y]=1;
    for(int i=0;i<4;i++)
    {  int xx=dx[i]+x;
       int yy=dy[i]+y;
       if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy]){
          dfs(xx,yy);
          s[x][y]=max(s[x][y],s[xx][yy]+1);
       }
    }
    return s[x][y];
}
int main()
{   
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
       scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        ans=max(ans,dfs(i,j));
    printf("%d",ans);
    return 0;
}

早些时候写的，码风……

by Jason_Teng @ 2024-10-07 19:52:05

@chenhouye 裸搜索！！！

by Super_Cube @ 2024-10-07 19:53:00

@chenhouye

int dp(int x,int y){
    if(b[x][y]!=0) return b[x][y];
    if(x<1||x>n||y<1||y>m) return 0;
    int mmm=1;
    for(int i=-1;i<=1;i++){
        for(int j=-1;j<=1;j++){
            if(i&&j)continue;
            int nx=x+i,ny=y+j;
            if((nx==x&&ny==y)||(a[nx][ny]>=a[x][y])) continue;
            mmm=max(mmm,dp(nx,ny)+1);
        }
    }
    b[x][y]=mmm;
    return mmm;
}

by chenhouye @ 2024-10-07 20:18:22

@Jason_Teng @Super_Cube
谢谢两位大佬，我竟然忘了不能斜向移动 我真傻

by Jason_Teng @ 2024-10-07 20:24:19

@Super_Cube 壶关？红名dalao