【BZOJ1017】魔兽地图

    树形DP，f[i][j][k]表示第i个装备，留j个用于更高级的装备的合成，花费k的钱获得最大的力量值。

    枚举合成装备x共l件，g[i][j]表示合成l件x装备的情况下，x的前i个子树（所需低级装备）用j的钱还能最多获得多大的力量值。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const int maxn=55,maxm=2010,maxlim=110,inf=~0U>>1,ninf=-(inf>>2);
inline char readchar() {char ch;while ((ch=getchar())==' ' || ch=='\n');return ch;}
inline void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

struct Equipment
{
	int c[maxn],t[maxn],cs;
	int str,cost,lim;
	int type;
}E[maxn];

int f[maxn][maxlim][maxm],g[maxn][maxm];
int degree[maxn];
int root;
int n,m;

void Calc_G(int x,int l)
{
	for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) g[i][j]=ninf;
	g[0][0]=0;
	for (int i=1;i<=E[x].cs;i++)
	for (int j=0;j<=m;j++)
	for (int k=l*E[x].t[i]*E[E[x].c[i]].cost;k<=j;k++)
		g[i][j]=max(g[i][j],g[i-1][j-k]+f[E[x].c[i]][l*E[x].t[i]][k]);
}

void Calc_F(int x,int l)
{
	for (int i=0;i<=l;i++)
	for (int j=l*E[x].cost;j<=m;j++)
		f[x][i][j]=max(f[x][i][j],g[E[x].cs][j]+(l-i)*E[x].str);
}

void DP(int x)
{
	if (E[x].type==0)
	{
		for (int i=0;i<=E[x].lim;i++)
		for (int j=i*E[x].cost;j<=m;j++)
		f[x][i][j]=min(j/E[x].cost-i,E[x].lim-i)*E[x].str;
		return;
	}
	
	for (int i=1;i<=E[x].cs;i++) DP(E[x].c[i]);
	E[x].lim=inf;
	for (int i=1;i<=E[x].cs;i++)
	{
		E[x].lim=min(E[x].lim,E[E[x].c[i]].lim/E[x].t[i]);
		E[x].cost+=E[x].t[i]*E[E[x].c[i]].cost;
	}
	E[x].lim=min(E[x].lim,m/E[x].cost);

	for (int l=0;l<=E[x].lim;l++)
	{
		Calc_G(x,l);
		Calc_F(x,l);
	}
}

void Init()
{
	read(n),read(m);
	for (int i=0;i<=n;i++)
	for (int j=0;j<=maxlim;j++)
	for (int k=0;k<=maxm;k++)
	f[i][j][k]=ninf;
	for (int i=1;i<=n;i++)
	{
		read(E[i].str);
		if (readchar()=='B')
		{
			E[i].type=0;
			read(E[i].cost),read(E[i].lim);
			E[i].lim=min(E[i].lim,m/E[i].cost);
		}
		else
		{
			read(E[i].cs);
			for (int j=1;j<=E[i].cs;j++) read(E[i].c[j]),read(E[i].t[j]),degree[E[i].c[j]]++;
			E[i].type=1;
		}
	}
	for (int i=1;i<=n;i++) if (!degree[i]) root=i;
}

void Print()
{
	int ans=0;
	for (int i=1;i<=n;i++) ans=max(ans,f[i][0][m]);
	printf("%d\n",ans);
}

int main()
{
	Init();
	DP(root);
	Print();
	return 0;
}