社区讨论

为何将dp数组初始化为-inf后答案才是正确的

P2014[CTSC1997] 选课参与者 3已保存回复 4

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@mhjb087y
此快照首次捕获于
2025/11/03 23:37
4 个月前
此快照最后确认于
2025/11/03 23:37
4 个月前
查看原帖
Code:
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=350;
int n,m;
int s[N],dp[N][N];
vector<int> g[N];
void dfs(int x){
	dp[x][1]=s[x];
	for (const auto &y:g[x]){
		dfs(y);
		for (int i=m;i>1;i--){
			for (int k=0;k<=i;k++){
				dp[x][i]=max(dp[x][i],dp[x][i-k]+dp[y][k]);
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	memset(dp,-0x3f3f3f,sizeof(dp)); //这里
	cin>>n>>m;
	m++;
	for (int i=1;i<=n;i++){
		int k;
		cin>>k>>s[i];
		g[k].push_back(i);
	}
	dfs(0);
	cout<<dp[0][m];
	return 0;
}
如果我不初始化 dp 数组,样例就输出 15,加上了就输出13,但是我不能理解为何需要初始化为负值。

回复

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

正在加载回复...