[树形DP] BZOJ1017 [JSOI2008]魔兽地图DotR

树形 \(DP\) 。容易想到 \(f(i,j,k)\) 表示以 \(i\) 为根的子树,共花了 \(k\) 金币,\(i\) 物品留了 \(j\) 个,的最优力量值。

转移就是类似背包搞一搞... 枚举合成 \(i\) 个:

定义 \(g(t)\) 表示用 \(t\) 金币,合成 \(i\)\(x\) 的最大力量值,把儿子的 \(f(son,w_{e}i,*)\) 暴力合并起来得到。

然后把一些留下,一些转化成价值,更新 \(f\) 就好了。

复杂度估起来爆炸,但远远跑不满。注意一下各种范围,就能很快了。

为什么一道 \(SD\) 题我调了这么久... \(g\) 开一维会奥妙重重的 \(WA\) 掉... 还是要直接,保险一点吧...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<cstring>
using namespace std;
int n,rt,M,ans,p[55],cnt[55],cst[55],mcst[55],pre[55],INF;
int f[55][105][2005],g[55][2005]; // f(i,j,k) 留 j 个给上面,花费 k ,贡献和最大
int fir[55],son[55],nxt[55],w[55],tot;
inline void add(int x,int y,int z){
son[++tot]=y; w[tot]=z; nxt[tot]=fir[x]; fir[x]=tot;
}
inline int min(int x,int y){ return x<y?x:y; }
inline int max(int x,int y){ return x>y?x:y; }
void dfs_info(int x){
if(!fir[x]){
cnt[x]=min(cnt[x],M/cst[x]), mcst[x]=min(cnt[x]*cst[x],M);
return;
}
cnt[x]=1e9;
for(int j=fir[x];j;j=nxt[j]){
dfs_info(son[j]);
if(cst[x]<=M) cst[x]+=cst[son[j]]*w[j];
mcst[x]+=mcst[son[j]]; cnt[x]=min(cnt[x],cnt[son[j]]/w[j]);
}
cnt[x]=min(cnt[x],M/cst[x]); mcst[x]=min(mcst[x],M);
}
void DP(int x){
if(!fir[x]){
for(int i=0;i<=cnt[x];i++)
for(int j=0;j<=i;j++) f[x][j][i*cst[x]]=(i-j)*p[x];
return;
}
for(int j=fir[x];j;j=nxt[j]) DP(son[j]);
for(int i=0;i<=cnt[x];i++){
g[0][0]=0; for(int j=1;j<=mcst[x];j++) g[0][j]=INF;
int o=0;
for(int j=fir[x];j;j=nxt[j]){
o++;
for(int k=0;k<=mcst[x];k++){
g[o][k]=INF;
for(int t=0;t<=k;t++)
g[o][k]=max(g[o][k],g[o-1][k-t]+f[son[j]][i*w[j]][t]);
}
}
for(int j=0;j<=i;j++)
for(int k=0;k<=mcst[x];k++)
f[x][j][k]=max(f[x][j][k],g[o][k]+(i-j)*p[x]);
}
}
int main(){
freopen("bzoj1017.in","r",stdin);
freopen("bzoj1017.out","w",stdout);
scanf("%d%d",&n,&M);
for(int i=1;i<=n;i++){
char typ[5]; scanf("%d%s",&p[i],typ);
if(typ[0]=='A'){
int t,x,y; scanf("%d",&t);
while(t--) scanf("%d%d",&x,&y), add(i,x,y), pre[x]=i;
} else scanf("%d%d",&cst[i],&cnt[i]);
}
++n; p[n]=0;
for(int i=1;i<=n-1;i++) if(!pre[i]) add(n,i,1);
dfs_info(n);
memset(f,192,sizeof(f)); INF=f[0][0][0];
DP(n);
for(int i=0;i<=M;i++) ans=max(ans,f[n][0][i]);
printf("%d",ans);
return 0;
}