题解 P4037 [JSOI2008] 魔兽地图
wind_seeker
·
·
题解
难得手切紫题，虽然时间复杂度倒数还是来写篇题解。
先不考虑优化这个逆天的 O(nm^2V)，V 为数量限制，我们设计状态：
考虑如何作背包，由于我们要统计最后合成了几个 $i$，所以我们要对每一个 $i$ 的个数单独处理，保证所有儿子加入的时候都是满足大于等于合成要求的。
于是开始转移：
对于 $f_{cur_u,u,i,j}$，枚举 $p\in[0,m]$，$q\in[j\times sum_v,num_v]$，其中 $sum_v$ 为合成一个 $u$ 所需要的 $v$ 的个数，$num_v$ 为最多可拥有的 $v$ 的个数。
则有：
$$f_{cur_u,u,i,j}=\max f_{pre_u,u,i-p,j}+f_{cur_v,v,p,q}$$
注意合成 $u$ 需要减去 $v$ 的力量值，所以一开始把拿去合成的 $v$ 都减去，最后在把所有合成的 $u$ 的力量值加回来。
```cpp
for(int i=0;i<=m;i++) for(int j=0;j<=num[u];j++) f[cur[u]][u][i][j]=-inf;
for(int i=0;i<=num[u];i++) f[cur[u]][u][0][i]=0;
void add(int v,int u){
swap(pre[u],cur[u]);
for(int i=0;i<=m;i++) for(int j=0;j<=num[u];j++) f[cur[u]][u][i][j]=-inf;
for(int j=0;j<=num[u];j++){
for(int i=0;i<=m;i++){
int V=i,W=-inf;
for(int k=j*sum[v];k<=num[v];k++) W=max(W,f[cur[v]][v][i][k]-(j*sum[v])*val[v]);
for(int k=m;k>=V;k--) f[cur[u]][u][k][j]=max(f[cur[u]][u][k][j],f[pre[u]][u][k-V][j]+W);
}
}
}
for(int j=0;j<=num[u];j++) for(int i=j*cost[u];i<=m;i++) f[cur[u]][u][i][j]+=val[u]*j;
```
这样只能拿下惨淡的 $60$ 分。接下来只需要把枚举 $p$ 的下界变为 $j\times sum_v\times cost_v$ 即可卡过去。
### code
```cpp
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2010,inf=1e9;
int n,m,in[N],f[2][60][N][110];
int val[N],cost[N],num[N],sum[N],pre[N],cur[N];
vector<int> e[N];
void add(int v,int u){
swap(pre[u],cur[u]);
for(int i=0;i<=m;i++) for(int j=0;j<=num[u];j++) f[cur[u]][u][i][j]=-inf;
for(int j=0;j<=num[u];j++){
for(int i=j*sum[v]*cost[v];i<=m;i++){
int V=i,W=-inf;
for(int k=j*sum[v];k<=num[v];k++) W=max(W,f[cur[v]][v][i][k]-(j*sum[v])*val[v]);
for(int k=m;k>=V;k--) f[cur[u]][u][k][j]=max(f[cur[u]][u][k][j],f[pre[u]][u][k-V][j]+W);
}
}
}
void dfs(int u){
pre[u]=1,cur[u]=0;
for(int i=0;i<=m;i++) for(int j=0;j<=num[u];j++) f[cur[u]][u][i][j]=-inf;
if(!e[u].size()) {for(int i=0;i<=m&&i/cost[u]<=num[u];i++) f[cur[u]][u][i][i/cost[u]]=i/cost[u]*val[u];return;}
for(auto v:e[u]){
dfs(v);
if(u==0) continue;
num[u]=max(num[u],num[v]/sum[v]),cost[u]+=sum[v]*cost[v];
}
for(int i=0;i<=num[u];i++) f[cur[u]][u][0][i]=0;
for(auto v:e[u]) add(v,u);
for(int j=0;j<=num[u];j++) for(int i=j*cost[u];i<=m;i++) f[cur[u]][u][i][j]+=val[u]*j;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++){
char op;
scanf("%d %c",&val[i],&op);
if(op=='B')
scanf("%d%d",&cost[i],&num[i]);
else{
scanf("%d",&x);
for(int j=1,v,y;j<=x;j++) scanf("%d%d",&v,&y),sum[v]=y,e[i].pb(v),in[v]++;
}
}
for(int i=1;i<=n;i++) if(!in[i]) e[0].pb(i);
dfs(0);int answer=-1;
for(int i=0;i<=m;i++) answer=max(answer,f[cur[0]][0][i][0]);
printf("%d\n",answer);
return 0;
}
/*
3 5
1 B 1 5
1 B 1 5
8 A 2 1 2 2 2
*/
```