社区讨论

今晚最后一晚了,求调个代码

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

正在加载回复...