P1434 [SHOI2002] 滑雪 （记忆化搜索

添加链接描述

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int mp[N][N];
int ans[N][N];
int dx[]={
    1,-1,0,0};
int dy[]={
    0,0,1,-1};
int n,m;
int dfs(int x,int y){
    
    // cout<<ans[i][j]<<"\n";
    int mx=0;
    if(ans[x][y]!=0)return ans[x][y];
    ans[x][y]=1;
    for(int i=0;i<4;i++){
    
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<=n&&nx>=1&&ny<=m&&ny>=1&&mp[nx][ny]<mp[x][y]){
    
            ans[x][y]=max(ans[x][y],dfs(nx,ny)+1);
            
        }
    }
    return ans[x][y];
}
int main(){
    
    
    cin>>n>>m ;
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=m;j++){
    
            cin>>mp[i][j];
        }
    }
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=n;j++){
    
            // cout<<"--\n";
            dfs(i,j);
        }
    }
    int mx=0;
    
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=n;j++){
    
            // cout<<ans[i][j]<<" ";
            mx=max(mx,ans[i][j]);
        }
        // cout<<"\n";
    }
    cout<<mx<<"\n";

    return 0;
}