首页 > 代码库 > 树形dp/hdu 1011 Starship Troopers

树形dp/hdu 1011 Starship Troopers

2024-07-28 06:45:28   220人阅读

题意

　　有n个房子，1号为起点房子。每个房子里会消耗一定的士兵来获取一定的价值。现在有m个士兵，求问可以获得的最大价值

　　注意：走过的房子不能再走

　　注意2：若要消灭这个房子的bugs，必须全部消灭

分析

　　典型的树形dp，01背包，因为每个房子里要么全杀死bugs，要么一个不动，只有取或不取两种状态

　　设f[i][j]表示以i为根节点，消耗j个士兵所能获得的最大价值

　　则f[i][j]=max(f[son[i]][k] + f[i][j-k]);

　　答案为f[1][m]

 

Accepted Code

 1 /* 2     PROBLEM:hdu1011 3     AUTHER:Nicole Lam 4     MEMO:树形dp 背包 5 */ 6 #include<cstdio> 7 #include<cstring> 8 using namespace std; 9 int n,m;10 int value[220],cost[220],bug[220],node[220];11 bool flag[110];12 int tree[220][220],f[220][220];13 14 int cmax(int x,int y)15 {16     return x>y?x:y;17 }18 19 void dfs(int x)20 {21     flag[x]=true;22     for (int i=cost[x];i<=m;i++) f[x][i]=value[x];23     for (int i=1;i<=node[x];i++)24     {25         int child=tree[x][i];26         if (!flag[child])27         {28             dfs(child);29             for (int j=m;j>=cost[x];j--)30                 for (int k=1;k+j<=m;k++)31                     if (f[child][k])32                     f[x][k+j]=cmax(f[x][k+j],f[x][j]+f[child][k]);33         }34     }35     return;36 }37 38 int main()39 {40     while (scanf("%d%d",&n,&m))41     {42         if (n==-1 && m==-1) break;43         memset(f,0,sizeof(f));44         memset(flag,0,sizeof(flag));45         memset(node,0,sizeof(node));46         for (int i=1;i<=n;i++)47         {48             scanf("%d%d",&bug[i],&value[i]);49             cost[i]=(bug[i]+19)/20;50         }51 52         int x,y;53         for (int i=1;i<n;i++)54         {55             scanf("%d%d",&x,&y);56             node[x]++;tree[x][node[x]]=y;57             node[y]++;tree[y][node[y]]=x;58         }59         if (m==0) printf("0\n");60         else61         {62             dfs(1);63             printf("%d\n",f[1][m]);64         }65     }66     return 0;67 }

 

　　

树形dp/hdu 1011 Starship Troopers


联系
我们