【codevs1378】选课——树形动规

题目传送门

这道题可以用多叉树转二叉树的方法，左子树为儿子，右子树为同个父亲的兄弟，这样的话就可以很方便地写出状态转移方程：

f[x][v]=max(f[x][v],w[x]+dp(ch[x][0],i)+dp(ch[x][1],v-i-1))；

要注意的是，f[x][v]可能在之前已经计算过（比如f[ch[i][0]][4]在f[i][5,6,7...]的时候就已经计算过）因此不必再计算，否则会TLE。

剩下的就不难了，直接DFS即可，具体实现细节看代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ch[305][2],w[305],fa,f[305][305];
int read(){
int ans=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0'; c=getchar();}
return ans*f;
}
int dp(int x,int v)
{
if(x==0)return 0;
if(f[x][v])return f[x][v];//DFS剪枝
for(int i=0;i<=v-1;i++)
f[x][v]=max(f[x][v],w[x]+dp(ch[x][0],i)+dp(ch[x][1],v-i-1));
f[x][v]=max(f[x][v],dp(ch[x][1],v));
return f[x][v];
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
fa=read();w[i]=read();
if(ch[fa][0])ch[i][1]=ch[fa][0];
ch[fa][0]=i;
}
int ans=dp(ch[0][0],m);
printf("%d",ans);
return 0;
}