首页 > 代码库 > hdoj1561The more, The Better(树形dp,依赖背包)

hdoj1561The more, The Better(树形dp,依赖背包)

题目:hdoj1561The more, The Better


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


分析:

分类:树形dp入门,依赖背包


做这题前又看了一遍背包9讲,感觉太经典了,尤其是泛化背包,简直是精华。这题的关系就是裸地依赖背包,用树形dp解。

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

定义状态:dp [ i ] [ j ] 表示在节点i,从以i为根节点的子树下选择j个城市的最大价值

初始化:dp [ i ] [ j ] =val [ i ](i节点的价值)(1 < = j < = m)

转移方程 dp【father】【j】 = max (dp【father】【j】,dp【father】【k】+dp【child】【j-k】);由前面的dfs可见,我们是用子节点更新父节点,用j枚举父节点选择的城市数,k枚举留给其他子节点选择城市数,那么就可以转移了


注意:此题出给很多初始节点,也就是有很多森林,我们要设置一个超级root连接子树的根节点即可。


代码:

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#define Del(a,b) memset(a,b,sizeof(a))
const int N = 150;
using namespace std;
int n,m;
int dp[N][N],vis[N];  //dp[i][j]表示在节点i,从以i为根节点的子树下选择j个城市的最大价值
int cap[N],val[N];
vector<int> v[N];

void creat(int o)
{
    for(int i=0; i<v[o].size(); i++)
    {
        int t=v[o][i];
        if(vis[t] == 0 && v[t].size()>0)
            creat(t);
        for(int j = m ; j > 1 ; j--)   //j>1表示此节点一定要取 0-1背包
        {
            for(int k=1; k<j; k++) //枚举给当前节点的其他子树留多少可选择的城市
                dp[o][j]=max(dp[o][j],dp[o][k]+dp[t][j-k]);
        }
    }
}

int main(){
    while(cin >> n >> m , n&&m){
        m ++; // 加一个根节点
        Del(dp,0);
        for(int i = 1 ; i <= n ; i ++){
            int a , b;
            cin >> a >> b;
            v[a].push_back(i);
            for(int j = 1 ; j <= m ; j++)
                dp[i][j] = b;  // 初始化时,每个节点,所有状态都是拿自己一个
        }
        creat(0);
        for(int i = 0 ; i <= n ; i ++)
            v[i].clear();
        cout << dp[0][m] << endl;
    }
    return 0;
}




hdoj1561The more, The Better(树形dp,依赖背包)