题目

https://www.luogu.org/problemnew/show/P2014
http://www.joyoi.cn/problem/tyvj-1051

解题思路

设 F[x][t] F [ x ] [ t ] 表式在以 x x 为根的子树中选tt门课能够获得的最高学分，设 x x 的子节点集合为Son(x)Son(x)，子节点个数 p=|Son(x)| p = | S o n ( x ) | 。 F[x][t]=0 F [ x ] [ t ] = 0 。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
struct node{int y,next;}a[1001];
int n,m,len,last[1001],f[1001][1001],c[1001];
void add(int x,int y)
{ a[++len]=(node){y,last[x]};last[x]=len;}
void dp(int x)
{
f[x][0]=0;
for (int i=last[x];i;i=a[i].next)
{
int y=a[i].y; dp(y);
for (int t=m;t>=0;t--)
for (int j=t;j>=0;j--)
if (t-j>=0) f[x][t]=max(f[x][t],f[x][t-j]+f[y][j]);
}
if (x!=0)
for (int t=m;t>0;t--) f[x][t]=f[x][t-1]+c[x];
}
int main()
{
scanf("%d%d",&n,&m);
int x;
for (int i=1;i<=n;i++)
{
scanf("%d%d",&x,&c[i]);
add(x,i);
}
dp(0);
printf("%d",f[0][m]);
}

最后

以上就是潇洒水池为你收集整理的[luogu 2014][tyvj 1051]选课｛背包类树形DP｝题目解题思路代码的全部内容，希望文章能够帮你解决[luogu 2014][tyvj 1051]选课｛背包类树形DP｝题目解题思路代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。