P2014 [CTSC1997] 选课

题目

P2014 [CTSC1997] 选课

算法标签: 动态规划, 树上$dp$

思路

非常显而易见的树上$dp$问题, 可以考虑状态表示$f[u][j]$代表以$u$为根节点的子树 分配$j$个节点的最大价值

树形$dp$解法代码

在递归之前先使用父节点更新当前节点信息, 在递归之后使用子节点更新父节点信息, 这样统计的信息是全面的

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 310, M = N << 1;

int n, m;
int head[N], ed[M], ne[M], idx;
int w[N];
int f[N][M];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u, int cnt) {
   
    if (cnt <= 0) return;
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        for (int k = 0; k < cnt; ++k) f[v][k] = f[u][k] + w[v];
        dfs(v, cnt - 1);
        for (int k = 1; k <= cnt; ++k) f[u][k] = max(f[u][k], f[v][k - 1]);
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
   
        int fa;
        cin >> fa >> w[i];
        if (fa) add(fa, i);
        else add(0, i);
    }

    dfs(0, m);
    int ans = f[0][m];
    cout << ans << "\n";
    return 0;
}

树上背包问题解法代码

定义状态表示$f[u][i][j]$表示以$u$为根节点的子树中考虑前$i$个子节点并且总的体积不超过$j$的所有方案中, 价值最大的方案, 因为是$dfs$进行状态转移, 可以像$01$背包问题一样优化掉一维, 但是第二维的体积需要反向枚举

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 310, M = N << 1;

int n, m;
int head[N], ed[M], ne[M], idx;
int f[N][M];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u) {
   
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        dfs(v);
        for (int j = m; j >= 0; --j) {
   
            for (int k = 0; k < j; ++k) {
   
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    m++;

    for (int i = 1; i <= n; ++i) {
   
        int fa;
        cin >> fa >> f[i][1];
        add(fa, i);
    }

    dfs(0);
    int ans = f[0][m];
    cout << ans << "\n";
    return 0;
}