原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1017
思路与代码参考：http://hzwer.com/5198.html
第一眼看到此题便能想到这是一件背包问题，但是鉴于其树形结构，不能直接求出每种物品最多能买的件数与每件物品的价格。
价格好说，直接将子树和相加即可。
至于最多购买的件数，能够肯定的是，每件物品的最多购买量，不会超过min{子物品的最大购买量/子物品的需求个数}
算出价格与件数，就能做背包了。
#include<cstdio>#include<cstring>const int inf=2147483647;using namespace std;void read(int &y){ ???y=0;char x=getchar(); ???while(x<‘0‘||x>‘9‘) x=getchar(); ???while(x>=‘0‘&&x<=‘9‘) ???{ ???????y=y*10+x-‘0‘; ???????x=getchar(); ???}}int min(int x,int y){ ???return x<y ? x : y;}int max(int x,int y){ ???return x>y ? x : y;}int n,m,cnt,tot,ans;int p[55],r[55],c[55];int f[55][105][2005];int g[55][2005],h[55][2005];char s[5];int last[55],deg[55];struct edge{ ???int to,next,v;}e[20005];void add(int u,int v,int w){ ???e[++cnt].to=v; ???e[cnt].next=last[u]; ???last[u]=cnt; ???e[cnt].v=w; ???deg[v]++;}void dp(int x){ ???if(!last[x]) ???{ ???????r[x]=min(r[x],m/c[x]); ???????for(int i=0;i<=r[x];i++) ???????{ ???????????for(int j=i;j<=r[x];j++) f[x][i][j*c[x]]=(j-i)*p[x]; ???????} ???????return; ???} ???r[x]=inf; ???for(int i=last[x];i;i=e[i].next) ???{ ???????dp(e[i].to); ???????r[x]=min(r[x],r[e[i].to]/e[i].v); ???????c[x]+=e[i].v*c[e[i].to]; ???} ???r[x]=min(r[x],m/c[x]); ???memset(g,-0x3f3f3f3f,sizeof(g)); ???g[0][0]=0; ???for(int l=r[x];l>=0;l--) ???{ ???????int tot=0; ???????for(int i=last[x];i;i=e[i].next) ???????{ ???????????tot++; ???????????for(int j=0;j<=m;j++) ???????????{ ???????????????for(int k=0;k<=j;k++) g[tot][j]=max(g[tot][j],g[tot-1][j-k]+f[e[i].to][l*e[i].v][k]); ???????????} ???????} ???????for(int j=0;j<=l;j++) ???????{ ???????????for(int k=0;k<=m;k++) f[x][j][k]=max(f[x][j][k],g[tot][k]+p[x]*(l-j)); ???????} ???}}int main(){ ???memset(f,-0x3f3f3f3f,sizeof(f)); ???read(n);read(m); ???for(int i=1;i<=n;i++) ???{ ???????read(p[i]); ???????scanf("%s",s); ???????if(s[0]==‘A‘) ???????{ ???????????int x;read(x); ???????????while(x--) ???????????{ ???????????????int v,num;read(v),read(num); ???????????????add(i,v,num); ???????????} ???????} ???????else read(c[i]),read(r[i]); ???} ???????for(int x=1;x<=n;x++) ???{ ???????if(deg[x]!=0) continue; ???????dp(x); ???????tot++; ???????for(int i=0;i<=m;i++) ???????{ ???????????for(int j=0;j<=i;j++) ???????????{ ???????????????for(int k=0;k<=r[x];k++) h[tot][i]=max(h[tot][i],h[tot-1][j]+f[x][k][i-j]); ???????????} ???????} ???} ???for(int i=0;i<=m;i++) ans=max(ans,h[tot][i]); ???printf("%d",ans); ???return 0;}
【bzoj1017】[JSOI2008]魔兽地图DotR
原文地址：http://www.cnblogs.com/zeroform/p/7642810.html