hdoj1010Starship Troopers （树状dp，依赖背包）

野性酷女 2022-09-20 15:25 109阅读 0赞

题目：[hdoj1010Starship Troopers ][hdoj1010Starship Troopers]

题意：有一个军队n个人要占领m个城市，每个城市有cap的驻扎兵力和val的珠宝，而且这m个城市的占领先后具有依赖关系，军队的每个人可以打败20个城市的防守者，而且占领城市后可以得到城市的珠宝，问最多可以得到多少珠宝？

分类：树形dp入门题，依赖背包

分析：是hdoj1561题目的复杂版，同样我们要构建一颗dp树，从叶子到根往上dp。

定义状态：dp【i】【j】 以节点 i 为根节点的子树，花费 j 的兵力可以得到的最大珠宝数。

状态转移方程：dp【father】【j】 = Max（dp【father】【j】，dp【father】【k】+dp【child】【j-k】）

注意：1：在一个节点即使只有没有兵力，也至少花费1的兵力攻占。

2：注意初始化

代码：

#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)
    {
        vis[o]=1;
        int tmp=(cap[o]+19)/20;
        if(tmp>m)
            return ;
        for(int i=tmp; i<=m; i++)
            dp[o][i]=val[o];
        for(int i=0; i<v[o].size(); i++)
        {
            int t=v[o][i];
            if(vis[t]==1)
                continue;
            if(v[t].size()>0)
            {
                creat(t);
                for(int j = m ; j > tmp ; j--)   //j>1表示此节点一定要取 0-1背包
                {
                    for(int k=0; k<=j-tmp; k++) //枚举给当前节点的其他子树留多少可选择的城市
                        dp[o][j]=max(dp[o][j],dp[o][j-k]+dp[t][k]);
                }
            }
        }
        if(dp[o][0]>0)//以u为根节点的子树至少要有一个人才可以获得该节点的brain
        {
            dp[o][1]=max(dp[o][1],dp[o][0]);
            dp[o][0]=0;
        }
    }
    
    int main()
    {
        while(cin >> n >> m )
        {
            if(n==-1 && m==-1)
                break;
            Del(dp,0);
            Del(vis,0);
            for(int i=1; i<=n; i++)
                scanf("%d%d",&cap[i],&val[i]);
            for(int i=1; i<n; i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                v[x].push_back(y);
                v[y].push_back(x);
            }
            creat(1);
            for(int i = 0 ; i <= n ; i ++)
                v[i].clear();
            cout << dp[1][m] << endl;
        }
        return 0;
    }

[hdoj1010Starship Troopers]: http://http://acm.hdu.edu.cn/showproblem.php?pid=1011