sloj P2006. 「树上背包」选课
题目描述
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
输入格式
第一行有两个整数N, M用空格隔开。( 1≤N≤300 , 1≤M≤300 )
接下来的N行,第I+1行包含两个整数ki和si，ki 表示第I门课的直接先修课，si表示第I门课的学分。若 ki=0 表示没有直接先修课（1≤ki≤N , 1≤si≤20）。
输出格式
只有一行，选M门课程的最大得分。
输入输出样例
输入 #17 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2输出 #1
13一道非常经典的dp问题，相信大家都做过了，但估计看到这的人都不会树形dp版会了你还看我干吗，还不去多刷几道 接下来谈正事 树形dp大部分都可以用记忆化搜索做的，相信大家这个都会，我就不多谈了 照例，挑战的原因是想作死 问题解析： 每门课程最多只有 1 门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱结点。 如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。 问题就转化： 在一个有 M 个结点的森林中选取 N 个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条件。 如图 1，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了 1 棵树， 选取结点时，从每个儿子出发进行选取。 这样看来这题和上题差不多：从根开始，把 M+1 个机会分配下去。状态也基本一样，f[i,j] 表示以i 为根的子树中选 j 门课能获得的最大学分。 但这题的树不是二叉的，不能像上题一样枚举分配，于是我们尝试将树转为二叉树，采取左儿子右兄弟的转换方法。具体做法参见代码 左儿子右兄弟写了个n2的蒟蒻 放心，代码里是O(n) 那么，不多说了，上代码
#include<bits/stdc++.h>
using namespace std;
struct edge{
int u,v,w,ne;
}e[100010];
int n,m,h[3010],dp[3010][3010],cnt,son[3010];
void add(int u,int v,int w){
cnt++;
e[cnt].u = u;
e[cnt].v = v;
e[cnt].w = w;
e[cnt].ne = h[u];
h[u] = cnt;
}
void f(int x){
for(int i = h[x];i;i = e[i].ne){
f(e[i].v);
son[x]+=son[e[i].v];
for(int j = son[x];j;j--)
for(int k = 1;k<=son[e[i].v]&&k<=j;k++)
dp[x][j] = max(dp[x][j],dp[x][j-k]+dp[e[i].v][k]-e[i].w);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n-m;i++){
int k,x,y;
scanf("%d",&k);
for(int j = 1;j<=k;j++){
scanf("%d%d",&x,&y);
add(i,x,y);
}
}
memset(dp,128,sizeof(dp));
for(int i = n-m+1;i<=n;i++){
int x;
scanf("%d",&x);
son[i] = 1;
dp[i][1] = x;
}
for(int i = 1;i<=n;i++)
dp[i][0] = 0;
f(1);
for(int i = m;i>=0;i--)
if(dp[1][i]>=0){
printf("%d",i);
break;
}
return 0;
}
标签：结点,洛谷,选课,P2014,cnt,int,课程,修课,dp From： https://www.cnblogs.com/cztq/p/16928186.html