BZOJ1017 魔兽地图DotR （树上背包）

一道背包的神题，用到了树上dp和背包dp，这个题的特殊性在于儿子对于父亲节点是有影响的，所以用f[i][j][k]表示第i号装备，其中用j个来合成上层装备，花费k元所能获得最大的力量值。

然后对于每一个节点枚举我选择合成几个，遍历每一个儿子节点，背包dp一下花费k元的最大力量值。注意这里的背包是一个分组背包，即对于每一个节点，我需要选择它的每一个叶子节点，这里每一个叶子都是一组物品（因为我需要枚举给每个叶子的花费），我需要选择每一组里的一个物品，所以是一个分组背包，最后用算出背包的g数组去更新f数组，同样是枚举话多少钱，把几个物品用于上层合成，然后转移状态。

——by VANE

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10-'0'+ch;ch=getchar();}
    return f*x;
}
int n,m,ans,TOT,cnt;
int P[55],L[55],M[55];
int f[55][105][2005];
int g[2005],h[2005];
char ch[5];
int last[55],deg[55];
struct date{int to,next,v;}e[20005];
void insert(int u,int v,int w)
{
    e[++cnt].to=v;e[cnt].next=last[u];
    last[u]=cnt;e[cnt].v=w;deg[v]++;
}
void dp(int x)
{
    if(!last[x])
    {
        L[x]=min(L[x],m/M[x]);
        for(int i=0;i<=L[x];++i)
            for(int j=i;j<=L[x];++j)
                f[x][i][j*M[x]]=(j-i)*P[x];
        return;
    }
    L[x]=inf;
    for(int i=last[x];i;i=e[i].next)
    {
        dp(e[i].to);
        L[x]=min(L[x],L[e[i].to]/e[i].v);
        M[x]+=e[i].v*M[e[i].to];
    }
    L[x]=min(L[x],m/M[x]);
    
    for(int l=L[x];l>=0;--l)
    {
        memset(g,-0x3f3f3f3f,sizeof g);g[0]=0;
        for(int i=last[x];i;i=e[i].next)
        {
            for(int j=m;j>=0;--j)
            {
                int t=-1e9;
                for(int k=0;k<=j;++k)
                    t=max(t,g[j-k]+f[e[i].to][l*e[i].v][k]);
                g[j]=t;
            }
                
        }
        for(int j=0;j<=l;++j)
            for(int k=0;k<=m;++k)
                f[x][j][k]=max(f[x][j][k],g[k]+P[x]*(l-j));
    }
}
int main()
{
    memset(f,-0x3f3f3f3f,sizeof f);
    n=read();m=read();
    for(int i=1;i<=n;++i)
    {
        P[i]=read();
        scanf("%s",ch);
        if(ch[0]=='A')
        {
            int x=read();
            while(x--)
            {
                int v=read(),num=read();
                insert(i,v,num);
            }
        }
        else M[i]=read(),L[i]=read();
    }
    for(int x=1;x<=n;++x)
    if(!deg[x])
    {
        dp(x);
        for(int i=m;i>=0;--i)
            for(int j=0;j<=i;++j)
                h[i]=max(h[i],h[j]+f[x][0][i-j]);
    }
    cout<<h[m];
}

BZOJ1017 魔兽地图DotR （树上背包）

相关推荐