洛谷 p2014 [CTSC2001] 选课 树形背包DP

题目：
https://www.luogu.org/problem/show?pid=2014

dp[i][j]：以i为根选j个物品（一定包括根）;

因为是森林,所以要建一个超级原点，把他们转化为一棵树;

怎么建？

因为n>=1;

所以，所有森林里的树的根的父亲默认为0,

so 不用建~~~~~（我纠结了很久QAQ）

先拓扑排序再DP（树形套路？？？）

边界：
所有dp[i][j]初始化为w[i]，以保证以i为根i一定被选上;

这样就变成了一个在拓扑序上做的普通01背包问题~~

关键是转化，转化后就挺简单了；

感觉老师讲复杂了（好吧，还是我太弱）;

方程：
dp[fa[x]][i]=max(dp[fa[x]][i-j]+dp[x][j],dp[fa[x]][i]);

注意三个问题:
1.m需要+1,因为0本身需要选上;
2.倒序更新，去掉后效性;
3.考虑dp[fa[x]][i-j]+dp[x][j]这句，fa[x]的i-j是否已包含x？
答案是否的，因为我们用要x更新它父亲，此前x与它父亲并无关联（因为是在拓扑序上DP），所以dp[fa[x]][i-j]中的i-j并不包含x，明白这点，这个题就很好理解了；
如果没有发现这个问题，说明还没有明白方程来龙去脉，再好好想想;

收获:
边界的巧妙设置~~;
转化的魅力~~~
拓扑排序消除后效性~~~；

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=20001;
int w[MAXN],dp[301][301],fa[MAXN],son[MAXN];
int n,m;
queue<int>q;
void top_sort()
{
while(!q.empty())
{
int x=q.front();
q.pop();
son[fa[x]]--;
if(!son[fa[x]]) q.push(fa[x]);
for(int i=m;i>=1;i--)
for(int j=i-1;j>=1;j--)
dp[fa[x]][i]=max(dp[fa[x]][i-j]+dp[x][j],dp[fa[x]][i]);
}
return;
}
void solve()
{
scanf("%d%d",&n,&m),m++;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&fa[i],&w[i]),son[fa[i]]++;
for(int j=1;j<=m;j++) dp[i][j]=w[i];
}
fa[0]=-1;
for(int i=1;i<=n;i++) if(!son[i]) q.push(i);
top_sort();
cout<<dp[0][m];
return;
}
int main()
{
solve();
return 0;
} 

最后

以上就是长情星星最近收集整理的关于洛谷 p2014 [CTSC2001] 选课 树形背包DP的全部内容，更多相关洛谷内容请搜索靠谱客的其他文章。