记忆化搜索90分第二个点TLE大佬帮忙看看

P1434 [SHOI2002] 滑雪

chichu @ 2022-10-04 21:04:00

#include<bits/stdc++.h>
using namespace std;
int a[101][101];
int R,C;
int mem[101][101];
int l[5]={0,-1,0,1,0};
int r[5]={0,0,1,0,-1};
int ans;
void dfs(int x,int y,int num){

    if(num<mem[x][y])
    return ;
    else mem[x][y]=num;

    int nx,ny;
    for(int i=1;i<=4;i++){

        nx=x+l[i];
        ny=y+r[i];

        if(nx>0&&nx<=R&&ny>0&&ny<=C&&a[nx][ny]<a[x][y])
        dfs(nx,ny,num+1);

    }
    ans=max(ans,num);
}
int main(){

    cin>>R>>C;
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++)
        cin>>a[i][j];
        }

    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++)
        dfs(i,j,1);
    }

    cout<<ans<<endl;
    return 0;
}

by bamboo12345 @ 2022-10-04 21:05:28

@chichu 有一个小优化:如果四周有比他高的那么他一定不是最好的,直接跳过


|