考察:树形dp
思路:
按划分给子节点的体积来分配集合.思路与苹果树大体相同.关于几个问题需要解释下:
- 为什么不和苹果树那题一样在遍历点的时候+w[vs]. 答: k不一定能装下,会使得背包里的价值多了
- 为什么要遍历完后特地加for(int i=m;i>=v[u];i--) f[u][i] = f[u][i-v[u]]+w[u]; 答:加上原本的父结点
- 为什么上面的循环是赋值而不是max.dfs循环里可能已经赋值了,但是我们不是必须放子节点,而是必须放根节点.
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 using namespace std; 6 const int N = 110; 7 int v[N],w[N],n,m,root,idx,h[N]; 8 int f[N][N]; 9 struct Road{ 10 int fr,to,ne; 11 }road[N]; 12 void add(int a,int b) 13 { 14 road[idx].fr = a,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++; 15 } 16 void dfs(int u) 17 { 18 for(int i=h[u];i!=-1;i=road[i].ne) 19 { 20 int vs = road[i].to; 21 dfs(vs); 22 for(int j=m-v[u];j>=0;j--)//给子树的空间不得多于减去放根节点的空间 23 for(int k=0;k<=j;k++) 24 f[u][j] = max(f[u][j],f[vs][k]+f[u][j-k]);//为什么不在这里加子节点体积,因为k可能放不下. 25 } 26 for(int i=m;i>=v[u];i--) f[u][i] = f[u][i-v[u]]+w[u]; 27 for(int i=0;i<v[u];i++) f[u][i] = 0; 28 } 29 int main() 30 { 31 memset(h,-1,sizeof h); 32 scanf("%d%d",&n,&m); 33 for(int i=1;i<=n;i++) 34 { 35 int p; 36 scanf("%d%d%d",&v[i],&w[i],&p); 37 if(p==-1) root = i; 38 else add(p,i); 39 } 40 dfs(root); 41 printf("%d\n",f[root][m]); 42 return 0; 43 }