社区讨论

关于本题(记忆化)

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 条回复,欢迎继续交流。

正在加载回复...