jzy_CSPJ_AK @ 2024-10-02 18:31:54

#include<bits/stdc++.h>
using namespace std;
int y[1500][1500],x[150][150],r,c,maxn=-1;
int dfs(int i,int j,int cnt){
    if(y[i][j]!=0)return y[i][j];
    y[i][j]=1;
    if(x[i+1][j]<x[i][j]&&i>=1&&j>=1&&i<r&&j<=c){
        y[i][j]=max(y[i][j],dfs(i+1,j,cnt+1));
    }
    if(x[i][j+1]<x[i][j]&&i>=1&&j>=1&&i<=r&&j<c){
        y[i][j]=max(y[i][j],dfs(i,j+1,cnt+1));
    }
    if(x[i-1][j]<x[i][j]&&i>=2&&j>=1&&i<=r&&j<=c){
        y[i][j]=max(y[i][j],dfs(i-1,j,cnt+1));
    }
    if(x[i][j-1]<x[i][j]&&i>=1&&j>1&&i<=r&&j<=c){
        y[i][j]=max(y[i][j],dfs(i,j-1,cnt+1));
    }
    maxn=max(maxn,cnt);
}
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>x[i][j];
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){

            dfs(i,j,1);
        }
    }
    cout<<maxn;
    return 0;
}

by Zenzenzense @ 2024-10-07 13:11:53

用记忆化```c

include<bits/stdc++.h>

using namespace std; inline void read(int &x){ char w=getchar(); int fl=1,sum=0; while(w>'9'||w<'0'){if(w=='-')fl=-1;w=getchar();} while(w<='9'&&w>='0'){sum=(sum<<1)+(sum<<3)+(w^48);w=getchar();} x=fl*sum; } string read_s() { string result; char w; while((w=getchar())!=EOF){ if(w=='\n') break; result+=w; } return result; } int r,c,mp[110][110],mem[110][110]; int ans; int dfs(int x,int y){ if (x<1||x>r||y<1||y>c){ return 0; } if (mem[x][y]!=0) { return mem[x][y]; } int maxLen=0; if(x<r&&mp[x+1][y]<mp[x][y]){ maxLen=max(maxLen,dfs(x+1,y)); } if(y<c&&mp[x][y+1]<mp[x][y]){ maxLen=max(maxLen,dfs(x,y+1)); } if(x>1&&mp[x-1][y]<mp[x][y]){ maxLen=max(maxLen,dfs(x-1,y)); } if(y>1&&mp[x][y-1]<mp[x][y]){ maxLen=max(maxLen,dfs(x,y-1)); } return mem[x][y]=maxLen+1; } int main(){ read(r);read(c); for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ read(mp[i][j]); } } for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ ans=max(ans,dfs(i,j)); } } cout<<ans<<endl; return 0; }

by Zenzenzense @ 2024-10-07 13:12:24

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
    char w=getchar();
    int fl=1,sum=0;
    while(w>'9'||w<'0'){if(w=='-')fl=-1;w=getchar();}
    while(w<='9'&&w>='0'){sum=(sum<<1)+(sum<<3)+(w^48);w=getchar();}
    x=fl*sum;
}
string read_s() {
    string result;
    char w;
    while((w=getchar())!=EOF){
        if(w=='\n') break;
        result+=w;
    }
    return result;
}
int r,c,mp[110][110],mem[110][110];
int ans;
int dfs(int x,int y){
    if (x<1||x>r||y<1||y>c){
        return 0;
    }
    if (mem[x][y]!=0) {
        return mem[x][y];
    }
    int maxLen=0;
    if(x<r&&mp[x+1][y]<mp[x][y]){
        maxLen=max(maxLen,dfs(x+1,y));
    }
    if(y<c&&mp[x][y+1]<mp[x][y]){
        maxLen=max(maxLen,dfs(x,y+1));
    }
    if(x>1&&mp[x-1][y]<mp[x][y]){
        maxLen=max(maxLen,dfs(x-1,y));
    }
    if(y>1&&mp[x][y-1]<mp[x][y]){
        maxLen=max(maxLen,dfs(x,y-1));
    }
    return mem[x][y]=maxLen+1;
}
int main(){
    read(r);read(c);
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            read(mp[i][j]);
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            ans=max(ans,dfs(i,j));
        }
    }
    cout<<ans<<endl;
    return 0;
}

@Zenzenzense