P4037 [JSOI2008] 魔兽地图 题解

· · 题解

P4037 [JSOI2008] 魔兽地图

比较难的树上背包题目。

题目中装备有购买限制，所以二维树上背包状态肯定无法表示。又由于每件装备的合成只与其子节点的合成数量有关，所以需要一维表示这一个装备合成多少个，这样刚好可以进行父子之间的转移。

设状态 f[x][y][z] 表示第 x 件装备合成 z 个，使用 y 个金币可以达到的最大价值。

初始时，f[x][y][z] 为负无穷。对于叶子节点，直接枚举购买数量，计算需要的金币，记录状态。

我们枚举 z，经过手推发现直接转移是不行的，所以考虑记录辅助转移数组 g[i][j] 表示第 x 件装备合成 z 个时，考虑到第 i 棵子树，使用了 j 个金币。

我们发现，每一棵子树都必须达到可以合成 z 个第 x 件装备的数量。也就是说，第 i 棵子树的装备至少合成 w_{x,i}\times z 个，且不能不选，其中 w_{x,i} 为合成 x 需要的 i 的数量。由于不能不选，所以 g[i][j] 的初值为负无穷，g[0][0]=0。

接下来，我们使用类似分组背包的转移方式。对于第 i 棵子树，在合成数量大于 w_{x,i}\times z 的情况下任意选择，也就是枚举这个子树使用的金币 k，合成的数量 l。易得如下转移方程：(s_{x,i} 为第 i 棵子树对应到的编号)

g[i][j]=\max(g[i-1][j],g[i][j-k]+f[s_{x,i}][j][l])(0\le k\le j,w_{x,i}\times z\le l \le 100)

上述过程可以使用滚动数组优化空间。转移结束后，令 f[x][y][z]=g[c_x][y]，其中 c_x 为 x 的子树数量，并计算合成的贡献。

这样做复杂度较高，为 O(100^2nm^2)。我们注意到如果倒序枚举 z，那么对于确定的 i,j，f[s_{x,i}][j][l] 组成的集合元素数量是单增不降的。我们可以使用一个变量来维护，就不需要枚举 l 了，时间复杂度为 O(100nm^2)。

这样还是会超时。我们发现其实对于一些高级装备，它们最多被合成的数量其实不大。我们可以把这个数量预处理出来，记为 y_x，z 就只需要从 y_x 枚举到 0 即可。

经过上述优化，代码成功通过此题。

#include <bits/stdc++.h>
using namespace std;
int n,m,c,x,ind[60],a[60],b[60],t[60],y[60],s[60][60],w[60][60],f[60][2001][101],g[2][2001],mx[60][2001],ans=-1e9;
char op;
void prework(int x)
{
    if(t[x]==0)return;
    y[x]=1e9;
    for(int i=1;i<=t[x];i++)
        {
        prework(s[x][i]);
        y[x]=min(y[x],y[s[x][i]]/w[x][i]);
        }
}

void dfs(int x)
{
    int now=0;
    if(t[x]==0)return;
    for(int i=1;i<=t[x];i++)dfs(s[x][i]);
    for(int i=1;i<=t[x];i++)
        for(int j=0;j<=m;j++)
            mx[s[x][i]][j]=-1e9;
    for(int i=1;i<=t[x];i++)
        for(int j=0;j<=m;j++)
            for(int p=(y[x]+1)*w[x][i];p<=100;p++)
                mx[s[x][i]][j]=max(mx[s[x][i]][j],f[s[x][i]][j][p]);
    for(int k=y[x];k>=0;k--)
        {
        for(int i=1;i<=t[x];i++)
            for(int j=0;j<=m;j++)
                if(k*w[x][i]<=100)
                   for(int p=k*w[x][i];p<=min((k+1)*w[x][i],100);p++)
                       mx[s[x][i]][j]=max(mx[s[x][i]][j],f[s[x][i]][j][p]);
        for(int j=0;j<=m;j++)g[now][j]=g[now^1][j]=-1e9;
        g[now][0]=0;
        for(int i=1;i<=t[x];i++)
            {
            for(int j=0;j<=m;j++)g[now^1][j]=-1e9;
            for(int j=0;j<=m;j++)
                for(int p=0;p<=j;p++)
                    g[now^1][j]=max(g[now^1][j],g[now][j-p]+mx[s[x][i]][p]);
            now^=1;
            }
        for(int i=0;i<=m;i++)
            if(g[now][i]!=-1e9)f[x][i][k]=g[now][i]+b[x]*k;
        }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=100;k++)
                f[i][j][k]=-1e9;
    for(int i=1;i<=n;i++)
        {
            cin>>a[i]>>op;
            if(op=='A')
                {
                    b[i]=a[i];
                    cin>>t[i];
                    for(int j=1;j<=t[i];j++)cin>>s[i][j],cin>>w[i][j],ind[s[i][j]]++;
                }
            else if(op=='B')
                {
                    cin>>c>>x;
                    y[i]=x;
                    for(int j=0;j<=x;j++)
                        if(c*j<=m)f[i][c*j][j]=a[i]*j;
                }
        }
    for(int i=1;i<=n;i++)
        if(t[i])
           for(int j=1;j<=t[i];j++)b[i]-=a[s[i][j]]*w[i][j];
    for(int i=1;i<=n;i++)
        if(ind[i]==0)prework(i);
    for(int i=1;i<=n;i++)
        if(ind[i]==0)dfs(i);
    for(int i=1;i<=n;i++)
        if(ind[i]==0)
           {
            for(int j=0;j<=m;j++)
                for(int k=0;k<=100;k++)
                    ans=max(ans,f[i][j][k]);
            cout<<ans;
           }
    return 0;
}