• 给定NN门课，每门课有自己的学分，可能有一门先修课
  • 不同的课程可能有共同的先修课
  • 求在学习课程项目限制MM内，可能获得的最大学分

存储

这题使用类似邻接表的方式存储树，对每一个节点，记录它的一个孩子节点，对于其他直连它的节点，使用邻接表串起来，对于没有先修课的节点，我们设置一个虚拟00节点。

  • 代码实现：
struct Tree {
    Tree *child, *next;
    int w;
    struct Answer {
        bool solved;
        int value;
        inline Answer(): solved(false) {}
    } ans[MAXM + 1];
    inline Tree() {}
    inline Tree(Tree *parent, int w): w(w), next(parent->child) {}
} trees[MAXN + 1];

树形DP

  • 设f(i,m)f(i,m)表示选择节点ii，并为节点ii的孩子节点和兄弟节点分配m−1m-1门选课机会所能获得的学分最大值，则有:
    1. 枚举kk，给节点ii的孩子节点分配kk门课，给节点ii的兄弟节点分配m−k−1m-k-1个节点，
    2. 不选择节点ii及其孩子节点，全部mm门课都分给它的兄弟节点
f(i,m)=max(maxk=0m−1(f(i.child,k)+f(i.next,m−k−1)),f(i,next,m)) f(i,m)=\max(\max\limits_{k=0}^{m-1}(f(i.child,k)+f(i.next,m-k-1)), f(i,next,m))

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 300;
const int MAXM = 300;
struct Tree {
    Tree *child, *next;
    int w;
    struct Answer {
        bool solved;
        int value;
        inline Answer(): solved(false) {}
    } ans[MAXM + 1];
    inline Tree() {}
    inline Tree(Tree *parent, int w): w(w), next(parent->child) {}
} trees[MAXN + 1];
int n, m;
void addEdge(int parent, int child, int w) {
    trees[parent].child = new (&trees[child]) Tree(&trees[parent], w);
}
inline int solve (Tree *t, int m) {
    if (!t || m < 0) return 0;
    if (!t->ans[m].solved) {
        t->ans[m].value = 0;
        for (int i = 0; i < m; i++) {
            t->ans[m].value = max(t->ans[m].value, solve(t->child, i) + solve(t->next, m - i - 1) + t->w);
        }//枚举k
        t->ans[m].value = max(t->ans[m].value, solve(t->next, m));
        t->ans[m].solved = true;
    }
    return t->ans[m].value;
}
int main () {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int parent, w;
        scanf("%d %d", &parent, &w);
        addEdge(parent, i, w);
    }
    printf("%d\n", solve(&trees[0], m + 1));//多了一门虚拟课，所以m+1
    return 0;
}