蒟蒻50分MLE求助,悬赏dalao关注!

P1434 [SHOI2002] 滑雪

crzcqh @ 2023-07-10 08:20:53

我也知道内存可能会过大,MLE,但不知道怎么解决。


#include<bits/stdc++.h>
using namespace std;
int n,m; 
int a[105][105],f[105][105]/*记忆化背包,也相当于记录每个点的答案*/,ans;
void dfs(int x,int y,int s){
    if(x<1||x>n||y<1||y>m) return;
    if(a[x][y]<s) return ;
    if(f[x][y]) return ;
    dfs(x+1,y,a[x][y]);
    dfs(x-1,y,a[x][y]);
    dfs(x,y+1,a[x][y]);
    dfs(x,y-1,a[x][y]);//搜索四个方向
    f[x][y]=max(
        max(f[x+1][y],f[x-1][y]),
        max(f[x][y+1],f[x][y-1])
    )+1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    } 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){//每个店都做起始点遍历一遍。
            dfs(i,j,a[i][j]);
            ans=max(f[i][j],ans);
        }
    }
    cout<<ans;
    return 0;
}

by Vocaloid世末歌者 @ 2023-07-10 08:25:36

@crzcqh 看着没问题啊,mle可能是dfs栈炸了


by crzcqh @ 2023-07-10 09:11:48

@CPlusPlusOnMars 那怎么办呢?


by LionBlaze @ 2023-07-10 09:45:08

我觉得是这样:如果相邻两个点高度相同,那么是过不去的,但是你的代码会一直在两个点之间徘徊。


by crzcqh @ 2023-07-10 09:50:56

@chenyikun2013 谢谢dalao! 所以加个vist可能就行了。


|