社区讨论
关于本题(记忆化)
P1434[SHOI2002] 滑雪参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mhizpquw
- 此快照首次捕获于
- 2025/11/03 18:21 4 个月前
- 此快照最后确认于
- 2025/11/03 18:21 4 个月前
为什么记忆化数组f初始化必须为-1,我初始化为其他的就会爆0
CPP#include<bits/stdc++.h>
#define ll long long
#define MAN 11451400
#define INF 1e18
using namespace std;
ll r,c,s;
ll a[150][150];
ll f[150][150];
ll dfs(ll x,ll y){
if(x<1||y<1||x>r||y>c) return 0;
if(f[x][y]!=-INF) return f[x][y];
ll ans=0;
if(a[x][y]>a[x-1][y]) ans=max(ans,dfs(x-1,y));
if(a[x][y]>a[x+1][y]) ans=max(ans,dfs(x+1,y));
if(a[x][y]>a[x][y-1]) ans=max(ans,dfs(x,y-1));
if(a[x][y]>a[x][y+1]) ans=max(ans,dfs(x,y+1));
return f[x][y]=ans+1;
}
int main(){
cin>>r>>c;
memset(f,-INF,sizeof(f));
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
cin>>a[i][j];
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
s=max(s,dfs(i,j));
cout<<s<<endl;
return 0;
}
如上为0分代码,但将其中的INF修改为-1后即可AC,求问原理
回复
共 2 条回复,欢迎继续交流。
正在加载回复...