这道题使我对树形DP有了新认识。

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

原题链接

Slove

每门课有一门或没有直接先修课，说明所有课程节点构成的图一定是树。
所以树形DP莽就完了。

d[i][j]表示以i为根节点的子树包含j个节点（不含根节点）时最大价值。
sz[i]表示以i为根节点的子树的节点数。
u为父节点，v为u的子节点。
对于以i为根节点的子树，d值来自两部分，一棵子树的值（d[v][k]）和其他子树的值(d[u][j-k-1])的和。因为j里面实际不包含节点v，所以再-1。
则转移方程为d[u][j]=max(d[u][j],d[u][j-k-1]+d[v][k]+s[v])，j<=sz[i],k<=sz[v]。

Tip

1. 没有直接先修课的，建立节点0为虚根，作为他们的父节点。
2. 这是树形背包。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 400
using namespace std;
int n,m;
int k[N],s[N];
int d[N][N];
int sz[N];
int first[N],nxt[N],to[N],len;
void add(int u,int v){
   to[++len]=v;
   nxt[len]=first[u];
   first[u]=len;
}
void dfs(int u){
   sz[u]=1;
   for(int i=first[u];i!=-1;i=nxt[i]){
   	dfs(to[i]);
   	sz[u]+=sz[to[i]];
   	for(int j=min(m,sz[u]);j>=0;j--){
   		for(int k=min(j-1,sz[to[i]]);k>=0;k--) d[u][j]=max(d[u][j],d[u][j-k-1]+d[to[i]][k]+s[to[i]]);
   	}
   }
}
int main()
{
   memset(first,-1,sizeof(first));
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++){
   	scanf("%d%d",&k[i],&s[i]);
   	add(k[i],i);
   }
   dfs(0);
   printf("%d",d[0][m]);
   return 0;
}