Luogu

BZOJ

分析

比较毒瘤的 DP 。

设$f[i][j][k]$表示第$i$件物品，有$j$个用于合成，总花费为$k$的最大力量值。

从子节点转移时是一个分组背包，需要再设$g[i][j]$表示前$i$棵子树花费为$j$能贡献给这个节点的最大价值。

然后直接转移就行了，详见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=51+10;
const int MAXM=2000+10;
const int INF=1e9;

int n,m;
int w[MAXN],c[MAXN],limit[MAXN];
int deg[MAXN];

struct Edge { int v,w,nxt; };
Edge e[MAXM];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

int f[MAXN][MAXN<<1][MAXM],g[MAXM];
int ans[MAXM];

inline void dfs(int u) {
    if (!head[u]) { //叶子节点
        limit[u]=min(limit[u],m/c[u]);
        for (re int i=0;i<=limit[u];++i)
            for (re int j=0;j<=i;++j)
                f[u][j][i*c[u]]=(i-j)*w[u];
        return;
    }
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        dfs(v);
        c[u]+=c[v]*w,limit[u]=min(limit[u],limit[v]/w);
    }
    limit[u]=min(limit[u],m/c[u]);
    for (re int i=0;i<=limit[u];++i) {
        memset(g,0xc0,sizeof(g)); g[0]=0;
        for (re int j=head[u];j;j=e[j].nxt) {
            int v=e[j].v,w=e[j].w;
            for (re int k=m;k>=0;--k) {
                int t=-INF;
                for (re int l=0;l<=k;++l)
                    t=max(t,g[l]+f[v][i*w][k-l]);
                g[k]=t;
            }
        }
        for (re int j=0;j<=i;++j)
            for (re int k=0;k<=m;++k)
                f[u][j][k]=max(f[u][j][k],g[k]+(i-j)*w[u]);
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) {
        char tmp[3];
        w[i]=read(); scanf("%s",tmp);
        if (tmp[0]=='B') c[i]=read(),limit[i]=read();
        else {
            int c=read(); limit[i]=INF;
            while (c--) {
                int v=read(),w=read();
                addEdge(i,v,w);
                ++deg[v];
            }
        }
    }
    memset(f,0xc0,sizeof(f));
    for (re int i=1;i<=n;++i) {
        if (deg[i]) continue;
        dfs(i);
        for (re int j=m;j>=0;--j)
            for (re 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;
}