树形dp可能是最优美的dp了……
这是一道经典的树上背包问题，考虑两种做法。第一种是直接在树上做一遍背包问题，另一种是把这棵树转化成“左儿子右兄弟”的二叉树，再做一遍背包问题。
方法一：我们定义f[i][j]表示以i为根的子树，一共选j门课最大的分数，那么我们可以得到f[i][j]=max(f[i][j-k]+f[x][k]) 其中x∈son(i).将这棵树遍历一遍即可求解。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 int n,m,s[310]; 7 vector<int> a[310]; 8 int f[310][310]; 9 void dfs(int now) { 10 f[now][0]=0; 11 for(int i=0;i<a[now].size();i++) { 12 int to=a[now][i]; 13 dfs(to); 14 for(int j=m;j>=0;j--) 15 for(int k=j;k>=0;k--) 16 f[now][j]=max(f[now][j],f[now][j-k]+f[to][k]); 17 } 18 if(now) { 19 for(int i=m;i>=1;i--) 20 f[now][i]=f[now][i-1]+s[now]; 21 } 22 } 23 int main() { 24 cin>>n>>m; 25 for(int i=1,x;i<=n;i++) { 26 cin>>x>>s[i]; 27 a[x].push_back(i); 28 } 29 memset(f,0xcf,sizeof(f)); 30 dfs(0); 31 cout<<f[0][m]<<endl; 32 return 0; 33 }
方法二：将这棵树转化为“左儿子右兄弟”的二叉树，此时f[i][j]表示在新的二叉树当中，f[i][j]表示以i为根的子树，一共选j门课最大的分数。那么分两种情况讨论。
我们在这两种决策当中取最优即可。
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 template <typename T> 5 T max(T x,T y) 6 { 7 return x>y?x:y; 8 } 9 inline int read() { 10 int ret=0,f=1; 11 char c=getchar(); 12 while(c<‘0‘||c>‘9‘) { 13 if(c==‘-‘) f=-1; 14 c=getchar(); 15 } 16 while(c<=‘9‘&&c>=‘0‘) { 17 ret=ret*10+c-‘0‘; 18 c=getchar(); 19 } 20 return ret*f; 21 } 22 int n,m,so[310],br[310]; 23 int f[310][310],val[310]; 24 inline void add(int father,int son) { 25 br[son]=so[father]; 26 so[father]=son; 27 } 28 int dfs(int i,int j) { 29 if(i==-1) return 0; 30 if(j==0) return 0; 31 if(f[i][j]!=-1) return f[i][j]; 32 int ret=-1<<30; 33 ret=max(ret,dfs(br[i],j)); 34 for(int k=0;k<=j-1;k++) 35 ret=max(ret,dfs(so[i],k)+dfs(br[i],j-k-1)+val[i]); 36 return f[i][j]=ret; 37 } 38 int main() { 39 n=read(); m=read(); 40 memset(so,-1,sizeof(so)); 41 memset(br,-1,sizeof(br)); 42 memset(f,-1,sizeof(f)); 43 for(int i=1;i<=n;i++) { 44 int x; 45 x=read(); 46 val[i]=read(); 47 add(x,i); 48 } 49 printf("%d\n",dfs(0,m+1)); 50 return 0; 51 }
原文：https://www.cnblogs.com/shl-blog/p/10700674.html
