洛谷P2014 [CTSC1997]选课

题目链接

一道树形背包问题

可以把每个子结点看作一个物品 $i$ 。设 $f[i][j][k]$ 为对于子树 $i$ 的前 $j$ 个结点中，选择 $k$ 个结点所能获得的最大价值

那么我们就可以根据01背包来得到状态转移方程：

$$f[i][j][k]=\max(f[son][node\_cnt][k],f[i][j-1][k-l])$$

在递归到i结点时，$son$ 结点的所有值都已求出，可以直接使用

循环到j时，已经求出 $j-1$ 条边的答案，所以循环顺序也不会影响答案

---

普通的01背包可以滚动数组来优化空间，那么树形背包可以吗？

当然可以！

在求解 $j$ 结点时，我们只需要用到 $j-1$ 结点和子树上的答案

那么就可以删掉数组的这一维，改变下循环顺序：

注意到，我们用到的 $j-1$ 结点的内容，都是满足 $k-l \leq k$ 的，所以只需要从大到小循环 $k$ 即可

---

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=305;
int n,m,cnt,head[maxn],f[maxn][maxn];
struct Edge{
	int to,nxt;
}a[maxn];
void add(int x,int y){a[++cnt]=(Edge){y,head[x]}; head[x]=cnt;}
void dfs(int x){
	for(int i=head[x];i;i=a[i].nxt){	//枚举每一棵子树 
		dfs(a[i].to);
		for(int j=n+1;j>=1;j--){		//当前结点选择了j个结点 
			for(int k=0;k<j;k++)		//子树上选择k个结点 
				f[x][j]=max(f[x][j],f[a[i].to][k]+f[x][j-k]);
		}
	}
}
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,i);
		f[i][1]=y;
	}
	dfs(0); 	//把0作为根结点纳入必选课程，再把要选择的课程数目+1即可 
	printf("%d\n",f[0][n+1]);
	return 0;
}