HDU1561 The more, The Better

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8490 Accepted Submission(s): 4964

Problem Description

ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？

Input

每个测试实例首先包括2个整数，N,M.(1 <= M <= N <=
200);在接下来的N行里，每行包括2个整数，a,b. 在第 i 行，a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡，如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量, b >= 0。当N = 0, M = 0输入结束。

Output

对于每个测试实例，输出一个整数，代表ACboy攻克M个城堡所获得的最多宝物的数量。

Sample Input

3 2

0 1

0 2

0 3

7 4

2 2

0 1

0 4

2 1

7 1

7 6

2 2

0 0

Sample Output

Author

8600

Source

HDU 2006-12 Programming Contest

Recommend

LL | We
have carefully selected several similar problems for you: 1011 2159 2639 1203 2602

分析：

典型的树形dp的题目。

首先，限制条件是选择m个物品，而每个物品最多选一次，跟0-1背包的区别在于有依赖关系，那么这层依赖关系我们可以借助于一个树来解决。借助dfs，从根节点开始dfs，然后直到叶子节点，回朔的时候进行0-1背包dp。

dp[i][j]表示以i为根节点取j个节点（包括根）的最优值
map[i][j]表示i号节点的第j个孩子是什么
num[i]表示i号节点的孩子数
vis[i]==0表示i号节点没有被访问

dp[i][j]=max(dp[i][j],dp[i][k]+dp[i的某个孩子节点][j-k])

表示在父亲节点i中选k个点和在i的某个孩子中选j-k个点

我们可以知道dp[i][1]=val[i]，因为选一个点的话必须选自己 = =

依赖关系形成森林，要先把树转换成森林才能进行树形DP

增加一个根节点0即可

答案即为dp[0][m+1]：因为增加了一个根节点

 #include<stdio.h>

 #include<string.h>

 int n,m;

 int num[];

 int  map[][];

 int dp[][];

 bool vis[];

 int max(int a,int b){

     return a>b?a:b;

 }

 void dfs(int p)

 {

     int i,j,k;

     //将p的访问置为true

     vis[p]=true;

     //遍历p的所有孩子

     for(i=;i<=num[p];i++)

     {

         //t是节点p的第i个孩子

         int t=map[p][i];

         //如果t没被访问，dfs它

         if(!vis[t]) dfs(t);

         //m反向过来是保证后面的数据不影响前面的，比如当m=5时，j=m，k=2时，等式右边出现过一次dp[p][2]

         //而当m=5时，j=2，k=2时， 状态转移方程等式左边出现了dp[p][2]，显然，这个出现的dp[p][2]不能影响右边那个dp[p][2]

         for(j=m;j>=;j--)//选择1个的状态不用更新了，就是节点本身，初始化中已经做了

         {

             for(k=;k<j;k++)//k表示父亲需要取的点的个数，j-k表示孩子需要取的点的个数

             {

                 //如果有值

                 if(dp[t][j-k]!=-&&dp[p][k]!=-)

                     dp[p][j]=max(dp[p][j],dp[p][k]+dp[t][j-k]);

             }

         }

     }

 }

 int main()

 {

     int i,j;

     while(scanf("%d%d",&n,&m),n||m)

     {

         int a,b;

         dp[][]=;

         memset(num,,sizeof(num));

         for(i=;i<=n;i++){

             scanf("%d%d",&a,&b);

             //初始化

             dp[i][]=b;

             map[a][++num[a]]=i;

         }

         m++;//增加一个点，森林转换成树

         //初始化

         for(i=;i<=n;i++){

             dp[i][]=;vis[i]=;

             for(j=;j<=m;j++){

                 dp[i][j]=-;

             }

         }

         dfs();

         printf("%d\n",dp[][m]);

     }

     return ;

 }

没过的代码：

错误：第30行的g[a][++num[a]]=i;这里写成了g[a][++num[i]]=i;

 #include <bits/stdc++.h>

 const int N=2e2+;

 using namespace std;

 int dp[N][N],m,n;

 int num[N],g[N][N];

 bool vis[N];

 void dfs(int r){

     vis[r]=true;

     for(int i=;i<=num[r];i++){

         int v=g[r][i];

         if(!vis[v]) dfs(v);

         for(int j=m;j>=;j--){

             for(int k=;k<j;k++){

                 //这里可以判断一下如果有值的话

                 if(dp[r][k]!=-&&dp[v][j-k]!=-)

                     dp[r][j]=max(dp[r][j],dp[r][k]+dp[v][j-k]);

             }

         }

     }

 }

 int main(){

     freopen("in.txt","r",stdin);

     memset(dp,-,sizeof(dp));

     while(scanf("%d %d",&n,&m),n||m){

         for(int i=;i<=n;i++){

             int a,w;

             cin>>a>>w;

             g[a][++num[a]]=i;//存孩子 //这里写成了g[a][++num[i]]=i;

             dp[i][]=w;

             dp[i][]=;

         }

         dp[][]=;

         dp[][]=;

         m++;

         dfs();

         cout<<dp[][m]<<endl;

     }

     return ;

 }

巴特西

HDU1561 The more, The Better

HDU1561 The more, The Better

分析：

最新文章

热门文章