Description
Input
Output
Sample Input
7 9 39 6 13 2 22 6 7 4 -19 5 28 6 -17 1 2 1 3 2 4 1 5 4 6 2 7 3
Sample Output
52
Data Constraint
Summary
这道题的模型是有依赖树形背包问题
我们把树的 dfs 序建出来,对于 dfs 序上每一个点,我们考虑如果自己选那么自己子树内就 可以选,否则只有在这棵子树外面才可以选。
设 f[i][j]表示 dfs 序第 i 个点及以后,费用总和为 j 的最大价值那么可以分第 i 个点选或不选进行转移
选:f[i][j]=max(f[i+1][j-w]+v)
不选:f[i][j]=max(f[i+size[x]][j]),其中 x 表示 dfs 序为 i 的那个点。
1 #include<cstdio> 2 #define N 2018 3 using namespace std; 4 struct arr{ 5 int x,y,next; 6 }s[N*3]; 7 int n,m,ans,l,v[N],p[N],ls[N],a[N],f[N][N],size[N]; 8 bool c[N]; 9 int ss(int x) 10 { 11 int i=ls[x]; 12 a[++l]=x; 13 while (i!=0){ 14 if (c[s[i].y]){ 15 c[s[i].y]=false; 16 ss(s[i].y); 17 size[x]+=size[s[i].y]; 18 } 19 i=s[i].next; 20 } 21 size[x]++; 22 } 23 24 int max(int a,int b){ 25 if (a>b) return a; 26 return b; 27 } 28 29 int main(){ 30 scanf("%d%d",&n,&m); 31 for(int i=1;i<=n;i++) 32 scanf("%d%d",&v[i],&p[i]); 33 for(int i=1;i<n;i++){ 34 scanf("%d%d",&s[i*2-1].x,&s[i*2-1].y); 35 s[i*2-1].next=ls[s[i*2-1].x]; 36 ls[s[i*2-1].x]=i*2-1; 37 s[i*2].x=s[i*2-1].y; 38 s[i*2].y=s[i*2-1].x; 39 s[i*2].next=ls[s[i*2].x]; 40 ls[s[i*2].x]=i*2; 41 } 42 for(int i=2;i<=n;i++) c[i]=true; 43 ss(1); 44 for(int i=0;i<=n+1;i++) 45 for(int j=0;j<=m;j++) 46 f[i][j]=-0xffffff; 47 f[1][0]=0; 48 for(int i=1;i<=n;i++){ 49 for(int j=0;j<=m;j++){ 50 if(j+p[a[i]]<=m){ 51 f[i+1][j+p[a[i]]]=max(f[i+1][j+p[a[i]]],f[i][j]+v[a[i]]); 52 f[i+size[a[i]]][j+p[a[i]]]=max(f[i+size[a[i]]][j+p[a[i]]],f[i][j]+v[a[i]]); 53 } 54 f[i+size[a[i]]][j]=max(f[i+size[a[i]]][j],f[i][j]); 55 } 56 } 57 int ans=0; 58 for(int j=0;j<=m;j++) 59 ans=max(ans,f[n+1][j]); 60 printf("%d",ans); 61 }