P2014 [CTSC1997]选课
题意为选一门课前要看它是否有前提条件：即选了一门主课才能选 “副科”，所以可以树形背包来做。
注意是不能用分组背包来做，因为这道题附件有很多个，光是两个附件的分组背包就需要四个转移方程，在这里根本没法做。
链式前向星建树。
本身这道题的数据是一组森林，但是森林很难一起dfs所以就把所有的树根都以0为根节点建一颗大树，直接链式前向星前序遍历即可。
本题最多能选M节课
转移方程 f[p][j]是指 f[以p为根节点][剩余可选课数]
因为每门课都只能选一次。所以类似01背包，因此倒序来压缩空间，从三维压缩到二维。
转移方程：
f[p][j]=max(f[p][j],f[v][k]+f[p][j−k])
就类似01背包拿当前节点的子节点或者不拿。（子节点是必须父节点被选上的时候才可以选子节点，所以用树形背包做）
解释的应该很清楚了，代码也非常简单，有问题的话就问我
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
using namespace std;
typedef long long ll;
const ll N=1e3+7;
const ll mod=2147483647;
const double EPS=1e-6;
struct node
{
ll u,v,pre;
}edge[N];
ll head[N],n,m,f[N][N],cnt;
inline void init()
{
memset(head,-1,sizeof head);
memset(f,0,sizeof f);
cnt=0;
}
inline void add(ll u,ll v)
{
edge[++cnt].pre=head[u];
edge[cnt].v=v;
head[u]=cnt;
}
inline void dfs(ll p)
{
for(int i=head[p];~i;i=edge[i].pre)
{
ll v=edge[i].v;
dfs(v);
for(int j=m+1;j>=1;--j)
{
for(int k=0;k<j;++k)
{
f[p][j]=max(f[p][j],f[v][k]+f[p][j-k]);
}
}
}
}
int main()
{
init();
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)
{
ll a,b;
scanf("%lld%lld",&a,&b);
f[i][1]=b;
add(a,i);
}
dfs(0);
printf("%lld\n",f[0][m+1]);
return 0;
}
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧
京公网安备 11010502036488号