90pts TLE on #2球条

P1434 [SHOI2002] 滑雪

lemon2312 @ 2024-11-24 21:45:49

#include<bits/stdc++.h>
using namespace std;
long long a[123][123],dx[]={10,0,1,0,-1},dy[]={10,1,0,-1,0};
long long n,m,st[123][123],ans,now,nx,ny;
int dfs(int x,int y){
    memset(st,0,sizeof(0));
    st[x][y]=1;
    for(int i=1;i<=4;i++){  
        int nx=dx[i]+x,ny=dy[i]+y;
        if(nx<1||ny<1||nx>n||ny>m||a[x][y]<=a[nx][ny]){
            continue;
        }else{
            dfs(nx,ny);
            st[x][y]=max(st[x][y],st[nx][ny]+1);
        }
    }
    return st[x][y];
}
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++){
            now=dfs(i,j);
            //cout<<now<<endl;
            ans=max(ans,now);
        }
    }
    cout<<ans;
    return 0;
}

by PENGQIXUAN_MR_P @ 2024-11-24 21:58:51

把边界判断试图挪到for外面,可以先无视边界搜,卡在边界里再return 0,应该会省一点时间


by H2O2_ @ 2024-11-24 23:15:44

@PENGQIXUAN_MR_P
不懂 ·‿·


by NirvanaCeleste @ 2024-11-25 17:30:05

@lemon2312加最优性剪枝 如果dp[i][j] > now 就不继续往下搜


by lemon2312 @ 2024-12-01 14:44:21

@NirvanaCeleste蟹蟹


|