20230921
P4037 [JSOI2008] 魔兽地图 sol
前言
历经千辛万苦终于调出来了，
细节不是有点多吧~
还参考了题解……
Statement
有 \(n\) 种装备，你有 \(m\) 块钱。装备的合成路线形成一棵树。叶子节点的装备需要用钱买，非叶子节点需要用它的儿子合成（对于一个儿子表示的装备，可能需要多个）。每种装备还有一定的数量限制，每个装备有一定的力量值。求力量值的和的最大值。
\(n \le 51, m \le 2000\)。
Solution
没有什么好的思路，
但很容易发现可以 dp。
我们用 \(f_{u,i,j}\) 表示当前节点 \(u\) 给上层提供 \(i\) 个装备，一共需要花 \(j\) 个金币的最大力量值。
注意 \(f\) 最开始要初始化成 \(-\infty\)。
于是对于每一棵树，我们都从它的根出发，不断往下 dfs 用树形 dp 求解，
代码已经很清楚明白，
注意一定要从树的根走下去！！！
#include <bits/stdc++.h>
using namespace std;
const int N=55,M=2e3+5,inf=1e9;
int n,m,w[N],val[N],cnt[N],head[N],tot=0,g[M],ans[M],f[N][N<<1][M],vv[N];
struct edge{
int v,nxt,w;
}e[N<<2];
bool vis[N];
char ch[5];
void add(int u,int v,int y){
e[++tot]=(edge){v,head[u],y};
head[u]=tot;vv[v]++;//vv是用来记录它是否有贡献，保证从根开始枚举！！！
}
void dfs(int u){
if(vis[u]) return ;
vis[u]=true;
if(!head[u]){
cnt[u]=min(cnt[u],m/w[u]);
for(int i=cnt[u];i>=0;i--)
for(int j=i;j<=cnt[u];j++)
f[u][i][j*w[u]]=val[u]*(j-i);
return ;
}
cnt[u]=inf;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
dfs(v);
cnt[u]=min(cnt[u],cnt[v]/e[i].w);
w[u]+=e[i].w*w[v];
}
cnt[u]=min(cnt[u],m/w[u]);
for(int i=cnt[u];i>=0;i--){
memset(g,-0x3f,sizeof(g));g[0]=0;
for(int j=head[u];j;j=e[j].nxt){
int v=e[j].v;
for(int k=m;k>=0;k--){
int res=-inf;
for(int p=0;p<=k;p++)
res=max(res,g[k-p]+f[v][i*e[j].w][p]);
g[k]=res;
}
}
for(int j=0;j<=i;j++)
for(int k=0;k<=m;k++)
f[u][j][k]=max(f[u][j][k],g[k]+val[u]*(i-j));
}
}
int main(){
/*2023.9.21 H_W_Y P4037 [JSOI2008] 魔兽地图 树形背包*/
scanf("%d%d",&n,&m);
memset(f,-0x3f,sizeof(f));
for(int i=1,x;i<=n;i++){
scanf("%d",&val[i]);
scanf("%s",ch);
if(ch[0]=='A'){
scanf("%d",&x);
for(int j=1,v,y;j<=x;j++){
scanf("%d%d",&v,&y);
add(i,v,y);
}
}
else scanf("%d%d",&w[i],&cnt[i]);
}
for(int i=1;i<=n;i++)
if(!vv[i]){
dfs(i);
for(int j=m;j>=0;j--)
for(int k=0;k<=j;k++)
ans[j]=max(ans[j],ans[j-k]+f[i][0][k]);
}
printf("%d\n",ans[m]);
return 0;
}
Conclusion
树形 dp 与背包的结合，看着办吧~
一定要注意初始化和细节！