社区讨论
为何将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 条回复,欢迎继续交流。
正在加载回复...