题目描述
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 (N) 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 (a) 是课程 (b) 的先修课即只有学完了课程 (a)，才能学习课程 (b)）。一个学生要从这些课程里选择 (M) 门课程学习，问他能获得的最大学分是多少？
输入格式
第一行有两个整数 (N) , (M) 用空格隔开。( (1 leq N leq 300) , (1 leq M leq 300) )
接下来的 (N) 行,第 (I+1) 行包含两个整数 (k_i) 和 (s_i) , (k_i) 表示第(I)门课的直接先修课，(s_i) 表示第I门课的学分。若 (k_i=0) 表示没有直接先修课（(1 leq {k_i} leq N) , (1 leq {s_i} leq 20)）。
输出格式
只有一行，选 (M) 门课程的最大得分。
输入输出样例
输入 #1
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出 #1
13
思路
这个题确实比较明显是一道树形dp，课与先修课之间的关系很明显是父节点与子节点之间的关系。用二维数组(f_{i,j})表示以(i)为根节点的子树选(t)门课的最大得分。下面考虑状态转移方程，然后会猛然发现，这好像是一个分组背包？！(t)门课相当于背包的容积，而子树就是分组。
但是dp要有根节点，我们并不知道选哪个课会最优，也就是无法确定根节点，那么我们就自己设一个虚拟根节点0，作为实际没有先修课的课程的先修课。这样0号结点就成为了整棵树的根节点，从0开始dp即可。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
int n,m,score[310];
vector<int> son[310];
int fa[310];
int f[310][310];//f[x][t]表示在以x为根的子树内选t门课程的最大得分
void dp(int x){
f[x][0]=0;//选0门课肯定得分为0
for(int i=0;i<son[x].size();i++){
int y=son[x][i];
dp(y);//遍历子树并递归
for(int t=m;t>=0;t--){//循环背包容积
for(int j=t;j>=0;j--){//循环组内物品
f[x][t]=max(f[x][t],f[x][t-j]+f[y][j]);
}
}
}
if(x!=0){//如果不是虚拟的0结点，那么还要更新
for(int t=m;t>0;t--){
f[x][t]=f[x][t-1]+score[x];
}
}//如果到了叶子结点那么只有这一层循环，相当于背包所以倒着循环。如果不是叶子结点也要更新，因为根节点必须选
}
int main()
{
scanf("%d%d",&n,&m);
memset(fa,-1,sizeof(fa));
for(int i=1,op;i<=n;i++){
scanf("%d%d",&op,&score[i]);
if(op!=0){
son[op].push_back(i);//建树
fa[i]=op;
}
}
for(int i=1;i<=n;i++){
if(fa[i]==-1){
son[0].push_back(i);//找到根节点
fa[i]=0;
}
}
dp(0);//dp
printf("%d
",f[0][m]);//输出以虚拟结点0为根节点的子树选m门课的最大得分
return 0;
}