貌似是很經典的樹形dp問題，應該說是樹形dp的入門！！
感覺樹形dp比背包多了一個輔助數組，背包直接一個數組循環下去，而樹形dp因為有分支，不是線性的，所以就需要用一個輔助數組來進行轉化最優情況！
1011 題目大意：一棵樹，有n個結點，每個結點有v個bug，有w的brain。我從1號結點開始走，帶著m個戰士。
1個戰士可以消滅20個bugs，如果我把某個結點的所有bug都消滅了我就能得到那個結點的brain。
如果想攻擊當前結點，那么必須先攻擊了它的父結點（1號點除外）。
其中當你攻占了當前結點，你可以分派人手，走向幾個不同的子結點，去攻占更多。也就是說，不是單一的路徑。
代碼：
1 # include<stdio.h>
2 # include<string.h>
3 # define N 105
4 struct node{
5 int from,to,next;
6 }edge[2*N];
7 int head[N],tol,visit[N],ans[N],bug[N],n,m,dp[N][N],f[N][N];
8 void add(int a,int b)
9 {
10 edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++;
11 }
12 int max(int a,int b)
13 {
14 return a>b?a:b;
15 }
16 void dfs(int u)
17 {
18 int i,j,r,tt,k;
19 visit[u]=1;
20 for(i=head[u];i!=-1;i=edge[i].next)
21 {
22 r=edge[i].to;
23 if(!visit[r])
24 {
25 dfs(r);
26 for(k=m;k>=1;k--)
27 {
28 for(j=1;j<=k;j++)
29 {
30 f[u][k]=max(f[u][k],f[u][k-j]+dp[r][j]);
31 }
32 }
33 /*for(j=0;j<=m;j++)
34 {
35 if(j*20>=ans[u])
36 dp[u][j]=max(dp[u][j],dp[r][(j*20-ans[u])/20]+bug[u]);
37 }*/
38 }
39 }
40 tt=(ans[u]+19)/20;
41 for(j=tt;j<=m;j++)
42 dp[u][j]=f[u][j-tt]+bug[u];
43 }
44 int main()
45 {
46 int i,a,b;
47 while(scanf("%d%d",&n,&m)!=EOF)
48 {
49 if(n==-1 && m==-1) break;
50 for(i=1;i<=n;i++)
51 scanf("%d%d",&ans[i],&bug[i]);
52 tol=0;
53 memset(head,-1,sizeof(head));
54 for(i=1;i<n;i++)
55 {
56 scanf("%d%d",&a,&b);
57 add(a,b);
58 add(b,a);
59 }
60 memset(visit,0,sizeof(visit));
61 memset(dp,0,sizeof(dp));
62 memset(f,0,sizeof(f));
63 if(m==0)
64 {
65 printf("0\n");
66 continue;
67 }
68
69 dfs(1);
70 printf("%d\n",dp[1][m]);
71 }
72 return 0;
73 }
1561 The more, The Better
題目意思不再解釋！
根據題意建立有向樹，父親節點優于孩子節點（必須先攻占父親節點才能攻占孩子節點）！
以0為樹根，求最優解的方法和上題一樣，只不過最后要求的是dp[0][m+1];
開始我沒想到把0作為根，那樣就會有很多棵樹，分別求出每棵樹的最優解，然后背包一次，也不錯！！
代碼：
View Code
1 # include<stdio.h>
2 # include<string.h>
3 # define N 205
4 int n,m;
5 struct node{
6 int from,to,next;
7 }edge[N];
8 int tol,head[N],visit[N],ans[N],dp[N][N],f[N][N];
9 void add(int a,int b)
10 {
11 edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++;
12 }
13 int max(int a,int b)
14 {
15 return a>b?a:b;
16 }
17 void dfs(int root)
18 {
19 int j,u,k,i;
20 visit[root]=1;
21 for(i=head[root];i!=-1;i=edge[i].next)
22 {
23 u=edge[i].to;
24 if(!visit[u])
25 {
26 dfs(u);
27 for(k=m;k>=0;k--)
28 for(j=0;j<=k;j++)
29 f[root][k]=max(f[root][k],f[root][k-j]+dp[u][j]);
30 }
31 }
32 for(j=1;j<=m+1;j++)
33 dp[root][j]=f[root][j-1]+ans[root];
34 }
35 int main()
36 {
37 int i,a,b;
38 while(scanf("%d%d",&n,&m)!=EOF)
39 {
40 if(n==0 && m==0) break;
41 tol=0;
42 memset(head,-1,sizeof(head));
43 for(i=1;i<=n;i++)
44 {
45 scanf("%d%d",&a,&b);
46 ans[i]=b;
47 add(a,i);
48 }
49 ans[0]=0;
50 memset(visit,0,sizeof(visit));
51 memset(dp,0,sizeof(dp));
52 memset(f,0,sizeof(f));
53 dfs(0);
54 printf("%d\n",dp[0][m+1]);
55 }
56 return 0;
57 }
浙公網安備 33010602011771號