社区讨论

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

P1434[SHOI2002] 滑雪参与者 5已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lo2mfnew
此快照首次捕获于
2023/10/23 16:13
2 年前
此快照最后确认于
2023/10/23 16:13
2 年前
查看原帖
CPP
#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)

回复

7 条回复,欢迎继续交流。

正在加载回复...