题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1017
好难想的状态啊！f[i][j][k]表示i号物品有j个向上贡献，一共花了k钱的最大力量；
g[i][j]用在子树中，表示前i个子树花j钱的最大值；
调了半上午，终于发现原来是少看了一个范围，f的第二维的范围不是51而是100啊啊啊啊啊啊！
除此之外此题也有很多要注意的地方，写在注释里了。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int const maxn=55,maxm=2005,inf=1000000000;int n,m,L[maxn],M[maxn],P[maxn],head[maxn],ct;int f[maxn][maxn<<1][maxm],g[maxn][maxm],rd[maxn],h[maxn][maxm];struct N{ ???int to,next,w; ???N(int t=0,int n=0,int w=0):to(t),next(n),w(w) {}}edge[20005];void dp(int x){ ???if(!head[x])//叶子 ????{ ???????L[x]=min(L[x],m/M[x]);//! ???????for(int i=0;i<=L[x];i++)//有i个 ????????????for(int j=0;j<=i;j++)//贡献j个 ????????????????f[x][j][M[x]*i]=P[x]*(i-j); ???????return;//!!!!!!!!!! ???} ???L[x]=inf;//!高级装备原本没有限制 ????for(int i=head[x],u;i;i=edge[i].next) ???{ ???????u=edge[i].to; ???????dp(u); ???????L[x]=min(L[x],L[u]/edge[i].w); ???????M[x]+=M[u]*edge[i].w;// ???} ???L[x]=min(L[x],m/M[x]); ???memset(g,-0x3f,sizeof g);//!! ???g[0][0]=0;//!! ???for(int l=L[x];l>=0;l--)//x物品有l个 ?//倒序! ?//l可以有0个！！！！！！！！！！！ ????{ ???????int tot=0;// ???????memset(g,0,sizeof g);//放在外面！ ????????for(int i=head[x],v;i;i=edge[i].next) ???????{ ???????????v=edge[i].to; ???????????tot++; ???????????for(int j=0;j<=m;j++)//一共有j钱 ????????????????for(int k=0;k<=j;k++)//给v k钱 ????????????????????g[tot][j]=max(g[tot][j],g[tot-1][j-k]+f[v][l*edge[i].w][k]); ???????????????????//g每次不会重新赋初值，所以需要l倒序来保证本次一定可以合成l个x物品 ????????} ???????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(){ ???scanf("%d%d",&n,&m); ???char dc;// ???memset(L,0x3f,sizeof L); ???memset(f,-0x3f3f3f3f,sizeof f); ???for(int i=1,x,a,b;i<=n;i++) ???{ ???????scanf("%d",&P[i]); ???????cin>>dc; ???????if(dc==‘A‘) ???????{ ???????????scanf("%d",&x); ???????????while(x--) ???????????{ ???????????????scanf("%d%d",&a,&b); ???????????????edge[++ct]=N(a,head[i],b);head[i]=ct; ???????????????rd[a]++; ???????????} ???????} ???????else scanf("%d%d",&M[i],&L[i]); ???} ???int tot=0; ???for(int i=1;i<=n;i++) ???????if(!rd[i]) ???????{ ???????????tot++; ???????????dp(i); ???????????for(int j=0;j<=m;j++) ???????????????for(int k=0;k<=j;k++) ???????????????????for(int l=0;l<=L[i];l++) ???????????????????????h[tot][j]=max(h[tot][j],h[tot-1][k]+f[i][l][j-k]); ???????} ???int ans=0; ???for(int j=0;j<=m;j++)ans=max(ans,h[tot][j]); ???printf("%d\n",ans); ???return 0;}bzoj1017 [JSOI2008]魔兽地图DotR——DP
原文地址：https://www.cnblogs.com/Zinn/p/9139072.html