题解 P4037 【[JSOI2008]魔兽地图】

· · 题解

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

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

安利blog

http://www.cnblogs.com/nbwzyzngyl/p/8287860.html
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,m,cnt,vv[N],head[N],v[N],f[N][105][2005],ans[2005],g[2005],L[N],p[N],M[N];
struct node{
    int to,nex,w;
}e[20005];
void add(int x,int y,int w)
{
    e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;e[cnt].w=w;vv[y]++;
}
void dp(int x)
{
    if(v[x])return;v[x]=1;
    if(!head[x]){
        L[x]=min(L[x],m/M[x]);
        for(int i=L[x];i>=0;--i)
        for(int j=i;j<=L[x];++j)
        f[x][i][j*M[x]]=p[x]*(j-i);
        return;
    }
    L[x]=1e9;
    for(int i=head[x];i;i=e[i].nex)
    {
        int y=e[i].to;dp(y);
        L[x]=min(L[x],L[y]/e[i].w);
        M[x]+=e[i].w*M[y];
    }
    L[x]=min(L[x],m/M[x]);
    for(int i=L[x];i>=0;--i)
    {
        memset(g,-0x3f,sizeof(g));g[0]=0;
        for(int j=head[x];j;j=e[j].nex)
        {
            int y=e[j].to;
            for(int a=m;a>=0;--a)
            {
                int t=-1e9;
                for(int b=0;b<=a;++b)
                t=max(t,g[a-b]+f[y][i*e[j].w][b]);
                g[a]=t;
            }
        }
        for(int j=0;j<=i;++j)
            for(int k=0;k<=m;++k)
            f[x][j][k]=max(f[x][j][k],g[k]+p[x]*(i-j));
    }
}
int main()
{
    memset(f,-0x3f,sizeof(f));
    scanf("%d%d",&n,&m);
    int k,x,y;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&p[i]);
        char s[3];scanf("%s",s);
        if(s[0]=='A'){
            scanf("%d",&k);
            for(int j=1;j<=k;++j)
            {
                scanf("%d%d",&x,&y);add(i,x,y);
            }
        }
        else{
            scanf("%d%d",&M[i],&L[i]);
        }
    }
    for(int i=1;i<=n;++i)
    if(!vv[i])
    {
        dp(i);
        for(int j=m;j>=0;--j)
        for(int k=0;k<=j;++k)
        ans[j]=max(ans[j],ans[j-k]+f[i][0][k]);
    }
    printf("%d\n",ans[m]);
    return 0;
}