社区讨论
今晚最后一晚了,求调个代码
P2014[CTSC1997] 选课参与者 3已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @m2oq5jb4
- 此快照首次捕获于
- 2024/10/25 20:44 去年
- 此快照最后确认于
- 2025/11/04 16:10 4 个月前
P2014
CPP#include <bits/stdc++.h>
#define N 301
#define M 301
#define INF 0x3f3f3f3f
using namespace std;
int n, m;
int k, s[N];
vector<int> edges[N];
int dp[N][M]; // 以i为根节点的子树中取j个的最大学分
int root[N], cnt = 0;
int siz[N];
void dfs(int p, int pre) {
for (int v : edges[p]) {
if (v != pre) {
dfs(v, p);
for (int i = siz[p] + 1; i >= 1; --i) {
for (int j = 1; j <= i; ++j) {
dp[p][i] = max(dp[p][i], dp[p][i - j] + dp[v][j]);
}
}
}
}
}
int main() {
cin >> n >> m;
memset(dp, -INF, sizeof(dp));
for (int i = 1; i <= n; ++i) {
cin >> k >> s[i];
dp[i][1] = s[i];
if (k == 0) {
++cnt;
root[cnt] = i;
} else {
edges[i].push_back(k);
edges[k].push_back(i);
++siz[i];
++siz[k];
}
}
for (int i = 1; i <= cnt; ++i) {
dfs(root[i], 0);
}
int maxx = -INF;
for (int i = 1; i <= n; ++i) {
maxx = max(maxx, dp[i][m]);
}
cout << maxx << endl;
return 0;
}
回复
共 8 条回复,欢迎继续交流。
正在加载回复...