真搞不懂为什么是90分,#2TLE

P1434 [SHOI2002] 滑雪

caojiaming @ 2023-05-09 21:13:22

#include <bits/stdc++.h>
using namespace std;
int n,m,h[110][110];
int ans=-1;
void dfs(int x,int y,int cnt,int lst)
{
    if(x>n||x<1||y>m||y<1)
    {
        return;
    }
    if(h[x][y]>=lst) return;
    ans=max(ans,cnt);

    lst=h[x][y];
    dfs(x+1,y,cnt+1,lst);
    dfs(x-1,y,cnt+1,lst);
    dfs(x,y+1,cnt+1,lst);
    dfs(x,y-1,cnt+1,lst);
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&h[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dfs(i,j,1,1e9);
        }
    }
    cout<<ans<<endl;
    return 0;
}

这是O(n²m²)复杂度对吧

n<=100,m<=100,

不正是10⁸吗?

那为什么还是TLE

(注:dfs遍历,只会把每个格子遍历一次,所以复杂度为nm)


by yzm0325 @ 2023-05-09 21:15:45

10^8就是Tle啊


by caojiaming @ 2023-05-09 21:17:00

@Zhuyiming0325

10^8就是计算机的速度,1s正好过


by yzm0325 @ 2023-05-09 21:20:34

@caojiaming 这个也很悬谁能说准那记搜(?

我太弱可能说不准


by yzm0325 @ 2023-05-09 21:21:43

到每个点的时候记录一下,再到这里时直接用这个结果(?


by zjw806903 @ 2023-05-26 19:12:16

也许你可以考虑用dp?


by naixvjiang @ 2023-05-27 11:01:00

考虑下记忆化或者回溯?


by fuck__luogu @ 2023-07-04 10:55:36

@caojiaming 谢谢你


|