社区讨论
真搞不懂为什么是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 条回复,欢迎继续交流。
正在加载回复...