HDU-4044 树形背包dp好题

佚名 6年前 (2019-04-21) 随笔 469人围观抢沙发百度已收录

不会做，题解是参考网上的。感觉这道题是到好题，使得我对树形背包dp更了解了。

有几个注意的点，直接给出代码，题解以及注意点都在注释里了。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int INF=0x3f3f3f3f;
int n,m,dp[N][N],p[N][N];
vector<int> G[N],P1[N],P2[N];

//对于背包问题，有代价为0的物品麻烦在于：状态转移时候还跟自己状态有关，所以本次状态先还不能改变，要用tmp先记录，转移完后才能改变 
void dfs(int x,int fa) {
    dp[x][0]=INF;
    //不建炮台的情况：分组背包（每个儿子就是一组背包，每组只能选一个物品）
    for (int i=0;i<G[x].size();i++) {  //一组物品 
        int y=G[x][i];
        if (y==fa) continue;
        dfs(y,x);
        for (int j=m;j>=0;j--) {  //容量 
            int tmp=0;
            for (int k=0;k<=j;k++)  //该组物品个数 
                tmp=max(tmp,min(dp[y][k],dp[x][j-k]));
            dp[x][j]=tmp;
        }
    }
    if (dp[x][0]==INF) dp[x][0]=0;
    //建炮台情况：注意只能建一个炮台 
    for (int i=m;i>=0;i--) {
        int tmp=dp[x][i];  //tmp是为了防止存在造价为0的炮台，否则直接用dp[x][i]会使得建立多个炮台 
        for (int j=0;j<P1[x].size();j++)
            if (i>=P1[x][j])
            tmp=max(tmp,dp[x][i-P1[x][j]]+P2[x][j]);   
        dp[x][i]=tmp;    
    }
}

int main()
{
    int T; cin>>T;
    while (T--) {
        cin>>n;
        for (int i=1;i<=n;i++) G[i].clear(),P1[i].clear(),P2[i].clear();
        for (int i=1;i<n;i++) {
            int x,y; scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        cin>>m;
        for (int i=1;i<=n;i++) {
            int l; scanf("%d",&l);
            for (int j=1;j<=l;j++) {
                int t1,t2; scanf("%d%d",&t1,&t2);
                P1[i].push_back(t1);
                P2[i].push_back(t2); 
            }
        }
        
        memset(dp,0,sizeof(dp));
        dfs(1,0);
        
        cout<<dp[1][m]<<endl;
    }    
    return 0;
}