P4037 [JSOI2008]魔兽地图（背包+树上背包）

· · 题解

P4037 [JSOI2008]魔兽地图

设P_x,L_x,M_x。表示物品 x 的能量，购买上限与价格。L_x=min（L_x，\frac {m}{M_x}）。从高级装备向合成它所需要的的低级装备连边，边权 w 为需要这种低级物品的数量。高级装备的 M 和 L 可以由低级装备推出。

设 f_{i,j,k}表示第 i 个物品，有 j 件用于上层的合成，花费金钱是 k 所能获得的最大力量。用 g_{i,j}表示 x 的前 i 个儿子的子树，花费 j 的钱，所能获得的最大力量。对于以 x 为根的子树，倒序枚举合成 l 个 x 物品（以保证每一轮所选取的 g_{tot-1,j-k}中所包含的决策至少选取了 l\times w 个物品用于合成），再用其余的钱买一些 x 子树内的装备不用于合成。g_{tot,j}=max \{ g_{tot-1,j-k}+f_{v,l\times w,k } \}。即从 j 中拿出 k 的钱在 v 的子树内购买。

最后再枚举合成的 l 个 x 物品中有 j 个是直接用于增加力量，剩余用于合成的f_{x,j,k}=max\{ g_{tot,k}+P_x\times (l-j)\}

代码和别的题解差不多。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct edg{
    int to,nxt,w;
}e[20005]; 
int cnt,head[55],f[55][105][2005],g[55][105][2005],L[55],M[55],P[55],n,m;
int ru[55],h[55][2005];
void add(int u,int v,int w)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].w=w;
    ru[v]++;
}
void dp(int u)
{
    if(!head[u])
    {//f[i][j][k]表示第i个物品，有j个用于合成上层，花费为k的最小代价 
        L[u]=min(L[u],m/M[u]);
        for(int i=0;i<=L[u];i++)//枚举上交i个 
            for(int j=i;j<=L[u];j++)//购买j个 
                f[u][i][j*M[u]]= (j-i)*P[u]; 
        return;
    }
    L[u]=0x3f3f3f3f;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        dp(v);
        L[u]=min(L[u],L[v]/e[i].w);
        M[u]+=e[i].w*M[v];
    }
    L[u]=min(L[u],m/M[u]);
    g[u][0][0]=0;
    for(int l=L[u];l>=0;l--)
    {
        int tot=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            tot++;
            int v=e[i].to;
            for(int j=0;j<=m;j++)//前tot个子树花了j块金币    
                for(int k=0;k<=j;k++)
                    g[u][tot][j]=max(g[u][tot][j],g[u][tot-1][j-k]+f[v][l*e[i].w][k]);
        }
        for(int j=0;j<=l;j++)
            for(int k=0;k<=m;k++)
                f[u][j][k]=max(f[u][j][k],g[u][tot][k]+(l-j)*P[u]);
    }
 } 
int main()
{
    scanf("%d%d",&n,&m);
    memset(f,-0x3f,sizeof(f));
    memset(g,-0x3f,sizeof(g));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&P[i]);
        char ch=getchar();
        while(ch!='A'&&ch!='B')ch=getchar();
        if(ch=='A')
        {
            int c;
            scanf("%d",&c);
            while(c--)
            {
                int v,w;
                scanf("%d%d",&v,&w);
                add(i,v,w);
            }
        }
        else scanf("%d%d",&M[i],&L[i]);
    }
    int tot=0,ans=0;
    for(int x=1;x<=n;x++)
    {
        if(!ru[x])
        {
            dp(x);
            tot++;
            for(int i=0;i<=m;i++)//前tot个子树花了i块金币    
                for(int j=0;j<=i;j++)
                    for(int k=0;k<=L[x];k++)
                        h[tot][i]=max(h[tot][i],h[tot-1][j]+f[x][k][i-j]);
        }
    }
    for(int i=0;i<=m;i++)
        ans=max(ans,h[tot][i]);
    printf("%d",ans);
    return 0;
}