hdu 1011 树型DP（依赖背包）

题意：你作为星河站队的leader，手下有m个trooper；现在让你去攻占一个基地：有n个洞穴组成，入口是洞穴1，洞穴之间用n-1条边链接，每个洞穴里面包括x个bugs,和他们的brains，你的每个trooper可以消灭20个bugs；问你最多可以得到多少个brains。

需要注意的是：你没做过的叶子必须要留人，也就是说就算某个地方的bug是0个，你也要牌一个trooper过去。

写这个题目的时候，开始用的是以前的依赖背包的思想，而且代码也是按照依赖背包写的，写的比较长，也比较繁琐，主要思路是：

因为入口是1，所以从1开始，设P=1，P是访问到的节点编号，设dp[i]表示i是需要的trooper数量，当作价格，dp[i]是得到的brains数量，当作价值：

1、遍历P的所有孩子，如果P的孩子i还有孩子，P=i，转到1，遍历完以后，如果所有的孩子都没有子孩子，转到2，否组转到3；

2、对所有的孩子进行01背包：初始化dp都是P的价值，然后进行01背包，然后把dp[i]对应的值都后移P的价格。因为如果想到到达P的孩子，必须到达P。然后回溯到上一层1，继续遍历P；

3、由于P的有些孩子还有孩子，那么处理的时候就要按照不同的情况进行01和分组背包处理，对于没有孩子的孩子，按照01背包处理，对于有孩子的孩子，对其进行分组背包的处理，然后回溯到上一层1继续遍历P；

代码如下：

/*#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define N 110
int num,total_price,dp[N][N];
struct Room{
    int price,value;
}room[N];
bool visited[N];
vector <int> connected[N];
void init()
{
    int i,x,y;
    memset(dp,sizeof(dp));
    memset(visited,true,sizeof(visited));
    for(i=0;i<=num;i++) connected[i].clear();
    for(i=1;i<=num;i++)
    {
        scanf("%d%d",&room[i].price,&room[i].value);
        room[i].price=ceil(room[i].price/20.0);
        if(room[i].price>total_price)        visited[i]=false;
    }
    for(i=1;i<num;i++)
    {
        scanf("%d%d",&x,&y);
        connected[x].push_back(y);
        connected[y].push_back(x);
    }
}
void dfs(int key)
{
    visited[key]=false;
    int i,j,k;
    for(i=room[key].price;i<=total_price;i++) dp[key][i]=room[key].value;
    for(i=0;i<(int)connected[key].size();i++)
    {
        int s=connected[key][i];
        if(!visited[s]) continue;
        dfs(s);
        for(j=total_price;j>=room[key].price;j--)
        {
            for(k=1;k+j<=total_price;k++)
            {
                if(dp[s][k])
                dp[key][j+k]=max(dp[key][j+k],dp[key][j]+dp[s][k]);
            }
        }
    }
}
int main()
{
    while(cin>>num>>total_price&&((num+1)||(total_price+1)))
    {
        init();
        if(!total_price)
        {
            cout<<"0"<<endl; continue;
        }
        dfs(1);
        cout<<dp[1][total_price]<<endl;
    }
}*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <list>
using namespace std;
#define N 105
struct Room{
    int price,value;
}room[N*N];
bool map[N][N],de_room[N],de_map[N];
list <int>tree[N];
int num,ans,num_i,num_j;
void update(int key)
{
    de_room[key]=false;
    int i;
    tree[key].clear();
    for(i=1;i<=num;i++)
    {
        if(map[key][i]&&de_room[i])
        {
            tree[key].push_back(i);
            de_room[i]=false;
        }
    }
    list <int>::iterator p=tree[key].begin();
    while(p!=tree[key].end())
    {
        update(*(p++));
    }
}
void fun(int key)
{
    int dp[N],i,k;
    memset(dp,sizeof(dp));
    list <int> ::iterator p=tree[key].begin();
    while(p!=tree[key].end())
    {
        if(tree[*p].empty())
        {
            k=0;
            if(room[*p].price==0)
            k=1;
            for(i=total_price;i>=room[*p].price+k;i--)
            {
                dp[i]=max(dp[i],dp[i-room[*p].price-k]+room[*p].value);
            }
        }
        else
        {
            fun(*p);
            for(i=total_price;i>=0;i--)
            {
                list <int> ::iterator q=tree[*p].begin();
                while(q!=tree[*p].end())
                {
                    if(i>=room[*q].price)
                    dp[i]=max(dp[i],dp[i-room[*q].price]+room[*q].value);
                    q++;
                }
            }
            tree[*p].clear();
        }
        p++;
    }
    tree[key].clear();
    if(key==num_i)
    {
        if(total_price-room[num_i].price>=0)
        ans=max(ans,dp[total_price-room[num_i].price]+room[num_i].value);
        return ;
    }
    for(i=total_price;i>=0;i--)
    {
        if(dp[i]<=0)
        {
            room[++num_j].price=room[key].price;
            if(room[key].price==0)
            room[num_j].price+=1;
            room[num_j].value=room[key].value;
            tree[key].push_back(num_j);
            break;
        }
        if(i+room[key].price<=total_price)
        {
            room[++num_j].price=i+room[key].price;
            room[num_j].value=dp[i]+room[key].value;
            tree[key].push_back(num_j);
        }
    }
}

int main()
{
    while(scanf("%d%d",&num,&total_price))
    {
        ans=0;
        if(num==-1&&total_price==-1)
        return 0;
        memset(de_map,sizeof(de_map));
        memset(map,false,sizeof(map));
        int i,y;
        for(i=1;i<=num;i++)
        {
            scanf("%d%d",&room[i].value);
            room[i].price=ceil(room[i].price/20.0);
            if(room[i].price>total_price)
            de_map[i]=false;
        }
        for(i=1;i<num;i++)
        {
            scanf("%d%d",&y);
            if(de_map[x]&&de_map[y])
            map[x][y]=map[y][x]=true;
        }
        if(total_price==0)
        {
            cout<<"0"<<endl;
            continue;
        }
        memset(de_room,sizeof(de_room));
        num_i=1;num_j=num;
        update(1);
        fun(1);
        cout<<ans<<endl;
    }
}

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define N 110
int num,&room[i].value);
        room[i].price=ceil(room[i].price/20.0);
        if(room[i].price>total_price)        visited[i]=false;//小小的优化，就是如果这个点的price比total_price还大，那么就不用访问了
    }
    for(i=1;i<num;i++)
    {
        scanf("%d%d",dp[key][j]+dp[s][k]);
            }
        }
    }
}
int main()
{
    while(cin>>num>>total_price&&((num+1)||(total_price+1)))
    {
        init();
        if(!total_price)
        {
            cout<<"0"<<endl; continue;
        }
        dfs(1);
        cout<<dp[1][total_price]<<endl;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!