[luogu 2014][tyvj 1051]选课｛背包类树形DP｝

题目

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

解题思路

设$F[x][t]$表式在以$x$为根的子树中选$t$门课能够获得的最高学分，设$x$的子节点集合为$Son(x)$，子节点个数$p=\left | Son(x) \right |$。$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]);
}