@ysner
2018-10-17T14:28:24.000000Z
字数 1787
阅读 2131
DP
树形DP
背包
感觉这道题是一道限制比较多的树形背包。
可以想见,所有装备之间的关系(合成就相当于树上指向)构成了森林。
然后对于合成关系,我们必须要考虑该装备有多少个用于合成其它装备,这样才能统计出该种装备实际贡献了多少力量值。
那么就设表示第种装备,向上贡献了个,实际合成花了元,其体系内装备所贡献的最大力量值。
各基本装备直接预处理。
对于高级装备,先枚举合成了个,然后再枚举在各儿子中各花了多少钱转移(它们的必须是合成个该装备要求的个数),这样才能背包处理出合成该装备所需的钱。
接下来就可以预处理高级装备的了。
最后还要对各棵树顶端的装备进行背包。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define re register
#define il inline
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=52,M=2002;
int n,m,val[N],cost[N],lim[N],dp[M],f[N][N*2][M],g[M];
char op[5];
bool Base[N];
vector<pair<int,int> >E[N];
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void dfs(re int u)
{
re int sz=E[u].size();
if(!sz)
{
lim[u]=min(lim[u],m/cost[u]);
fp(i,0,lim[u])
fp(j,0,i)
f[u][j][i*cost[u]]=val[u]*(i-j);
return;
}
lim[u]=1e9;
fp(i,0,sz-1)
{
re int v=E[u][i].fi,w=E[u][i].se;
dfs(v);
cost[u]+=cost[v]*w;lim[u]=min(lim[u],lim[v]/w);
}
lim[u]=min(lim[u],m/cost[u]);
fp(i,0,lim[u])
{
memset(g,-63,sizeof(g));g[0]=0;
fp(j,0,sz-1)
{
re int v=E[u][j].fi,w=E[u][j].se,tmp;
fq(k,m,0)
{
tmp=-1e9;
fp(l,0,k) tmp=max(tmp,g[l]+f[v][i*w][k-l]);
g[k]=tmp;
}
}
fp(j,0,i)
fp(k,0,m)
f[u][j][k]=max(f[u][j][k],g[k]+val[u]*(i-j));
}
}
int main()
{
n=gi();m=gi();
fp(i,1,n)
{
val[i]=gi();
scanf("%s",op);
if(op[0]=='A')
{
re int c=gi(),x,y;
fp(j,1,c) x=gi(),y=gi(),Base[x]=1,E[i].pb(mk(x,y));
}
if(op[0]=='B') cost[i]=gi(),lim[i]=gi();
}
memset(f,-63,sizeof(f));
fp(i,1,n)
if(!Base[i])
{
dfs(i);
fq(j,m,0)
fp(k,0,j)
dp[j]=max(dp[j],dp[j-k]+f[i][0][k]);
}
printf("%d\n",dp[m]);
return 0;
}