洛谷 P2014 CTSC1997 选课

url: https://www.luogu.com.cn/problem/P2014

tag:
动态规划，树形DP，CTSC/CTS，1997

思路：
和背包比较像，但是有一点区别的是对如果某个节点要选，也需要将其选不同数量节点的情况，分别更新，也就是说不知道每个点的“体积”是多少。因为要选一门课需要将其有依赖的课也选。所以需要从小更新到大。如果将0也算节点，那么整个结构会构成棵树，此时也需要让m ++，表示一共选m + 1个节点。最后输出 f[0][m] 表示选0时不超过m门课，最大的学分。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 400;
int n, m;
int h[N], e[N * 2], ne[N * 2], idx;
int s[N];
int f[N][N];
void add (int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u)
{
    f[u][1] = s[u];
    for (int i = h[u]; ~i; i = ne[i])
        dfs(e[i]);
    for (int i = h[u]; ~i; i = ne[i])
        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[e[i]][k]);
}
int main()
{
    cin >> n >> m;
    m ++;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++)
    {
        int a;
        cin >> a >> s[i];
        add(a, i);
    }
    dfs(0);
    cout << f[0][m] << endl;
    return 0;
}