「JSOI2008」魔兽地图

题意： $n$ 个物品，每个物品都有贡献值 $p _{i}$ 。物品分为基础物品和高级物品。基础物品的价格为 $val _{i}$ ，数量限制为 $l _{i}$ ；高级物品不需要额外花费，需要不同种不同数量的低级物品合成。现在你有 $m$ 个金币，如何购买和合成物品使贡献值最大。

经典的 树上背包 ！！！

对于每一级物品，他肯定由部分更低级的物品合成，且部分这一级的物品将会用于合成更高级的物品。即每一层受到更低一层的影响，同时影响上一层。

我们用 $d _{i,j,k}$ 表示第 $i$ 个物品，用 $j$ 个合成更高级的物品，预算为 $k$ 个金币的最大贡献值。从高级物品往合成它的低级物品连边建树，边权为需要这种低级物品的个数。对于基础物品，可以直接枚举向上传递的个数和买的总个数初始化。

l[u]=min(l[u],m/val[u]);
for(int i=l[u];i>=0;i--)
	for(int j=i;j<=l[u];j++)
	{
		if(j*val[u]>m)
			break;
		d[u][i][j*val[u]]=p[u]*(j-i);
	}
return ;

对于高级物品，我们先计算出它们的数量限制和价格。数量限制和价格都由低级物品的价格和所需数量决定。

l[u]=INF;
for(int i=head[u];i;i=e[i].next)
{
	int v=e[i].to;
	dfs(v);
	l[u]=min(l[u],l[v]/e[i].num);
	val[u]+=val[v]*e[i].num;
}
l[u]=min(l[u],m/val[u]);

接着考虑转移 $d$ 数组，转移方程分为两部分，第一部分枚举下一层向上传的个数，从下一层转移到这一层；第二部分枚举这一层向上传的个数，由这一层转移到上一层。

for(int i=l[u];i>=0;i--)
{
	memset(g,-0x3f,sizeof(g));
	g[0]=0;
	for(int j=head[u];j;j=e[j].next)
	{
		int v=e[j].to;
		for(int k=m;k>=0;k--)
		{
			int o=-INF;
			for(int l=0;l<=k;l++)
				o=max(o,g[k-l]+d[v][i*e[j].num][l]);
			g[k]=o;
		}
	}//第一部分
	for(int j=0;j<=i;j++)
		for(int k=0;k<=m;k++)
			d[u][j][k]=max(d[u][j][k],g[k]+p[u]*(i-j));//第二部分
}

对于第一部分， $i$ 表示下一层向上转移的个数， $k$ 表示这一层总花费， $l$ 表示由下层转移上来的花费；

对于第二部分， $i$ 表示这一层的总个数， $j$ 表示向上转移的个数， $k$ 表示这一层总花费。

由于两个转移的决策之间互相影响，所以要另开数组 $g$ 来转移，再赋值给 $d$ 数组。

最后由于根节点代表顶级装备，可能有很多顶级装备，即森林，其中每棵树的贡献为 $d _{i,0,k}$ ， $i$ 为顶级装备的编号， $k$ 为这棵树的花费。由于存在多棵树，因此还要再次背包一下。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=2010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,m,indgr[55],p[55],l[55],val[55];
int head[maxn<<1],cnt,vis[55],a[maxn],g[maxn];
int d[55][105][maxn],f[maxn];//d[i][j][k]表示第i个装备，用j个合成新装备，k个金币作为预算的最大贡献值。
struct node
{
	int next;
	int to;
	int num;
}e[maxn<<1];
void add(int from,int to,int num)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	e[cnt].num=num;
	head[from]=cnt;
}
void dfs(int u)
{
	if(vis[u])
		return ;
	vis[u]=1;
	if(!a[u])
	{
		l[u]=min(l[u],m/val[u]);
		for(int i=l[u];i>=0;i--)
			for(int j=i;j<=l[u];j++)
			{
				if(j*val[u]>m)
					break;
				d[u][i][j*val[u]]=p[u]*(j-i);
			}
		return ;
	}
	l[u]=INF;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		dfs(v);
		l[u]=min(l[u],l[v]/e[i].num);
		val[u]+=val[v]*e[i].num;
	}
	l[u]=min(l[u],m/val[u]);
	for(int i=l[u];i>=0;i--)
	{
		memset(g,-0x3f,sizeof(g));
		g[0]=0;
		for(int j=head[u];j;j=e[j].next)
		{
			int v=e[j].to;
			for(int k=m;k>=0;k--)
			{
				int o=-INF;
				for(int l=0;l<=k;l++)
					o=max(o,g[k-l]+d[v][i*e[j].num][l]);
				g[k]=o;
			}
		}
		for(int j=0;j<=i;j++)
			for(int k=0;k<=m;k++)
				d[u][j][k]=max(d[u][j][k],g[k]+p[u]*(i-j));
	}
}
int main()
{
	memset(l,0x3f,sizeof(l));
	memset(d,-0x3f,sizeof(d));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		char c;
		scanf(" %c",&c);
		if(c=='A')
		{
			a[i]=1;
			int q;
			scanf("%d",&q);
			for(int j=1;j<=q;j++)
			{
				int x,y;
				scanf("%d%d",&x,&y);
				add(i,x,y);
				indgr[x]++;
			}
		}
		else
			scanf("%d%d",&val[i],&l[i]);
	}
	for(int i=1;i<=n;i++)
		if(!indgr[i])//根节点
		{
			dfs(i);
			for(int j=m;j>=0;j--)
				for(int k=0;k<=j;k++)
					f[j]=max(f[j],f[j-k]+d[i][0][k]);
		}
	printf("%d",f[m]);
	return 0;
}