1017: [JSOI2008]魔兽地图DotR - BZOJ

Description

DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图,他的规则简单与同样流行的地图DotA (Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值,每件装备都可以使佩戴它的英雄的力量值提高固定的点数,所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买,而高级装备需要用基本装备或者较低级的高级装备来合成,合成不需要附加的金币。装备的合成路线可以用一棵树来表示。比如,Sange and Yasha的合成需要Sange, Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant Strength 和 Sange Recipe Scroll合成。每件基本装备都有数量限制,这限制了你不能无限制地合成某些性价比很高的装备。现在,英雄Spectre有M个金币,他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他吗?他会教你魔法Haunt(幽灵附体)作为回报的。
Input

输入文件第一行包含两个整数,N (1 <= n <= 51) 和 m (0 <= m <= 2,000)。分别表示装备的种类数和金币数。装备用1到N的整数编号。接下来的N行,按照装备1到装备n的顺序,每行描述一种装备。每一行的第一个正整数表示这个装备贡献的力量值。接下来的非空字符表示这种装备是基本装备还是高级装备,A表示高级装备,B表示基本装备。如果是基本装备,紧接着的两个正整数分别表示它的单价(单位为金币)和数量限制(不超过100)。如果是高级装备,后面紧跟着一个正整数C,表示这个高级装备需要C种低级装备。后面的2C个数,依次描述某个低级装备的种类和需要的个数。
Output

第一行包含一个整数S,表示最多可以提升多少点力量值。
Sample Input
10 59
5 A 3 6 1 9 2 10 1
1 B 5 3
1 B 4 3
1 B 2 3
8 A 3 2 1 3 1 7 1
1 B 5 3
5 B 3 3
15 A 3 1 1 5 1 4 1
1 B 3 5
1 B 4 3

Sample Output
33

 

看见我机房的小伙伴没写,我又不能问他,BZOJ上这又不是一道不可做题,不想跳过这道题,于是就写了

题解一共也就两种,一个是VFleaKing的,另一个是普通的树dp

看题解看不懂啊,囧,没办法,我就是这么弱........

于是先打暴力,f[i,j,k]表示节点i买了j个,用了k元钱的最大力量值

然后树dp之,对于每一个j,先强制买好j个i物品,然后k元钱里剩下的去做背包(从i的儿子里面选,用合成剩余的部分来做01背包)

暴力好不容易打出来(细节没注意,囧,写了一两个小时暴力,之前还想抄C++代码,可惜不怎么懂,勉强翻译过来连样例都过不了)

暴力肯定是要超时的(我自测,有的点100s都跑不出),不过我发现了一个优化

  1 const
  2         maxn=52;
  3         maxm=2001;
  4 var
  5         w,gold,lim,num,max1,fa,first:array[0..maxn]of longint;
  6         next,last:array[0..maxn*2]of longint;
  7         f:array[0..maxn,0..101,0..maxm]of longint;
  8         n,m,ans,tot:longint;
  9 
 10 procedure insert(x,y,z:longint);
 11 begin
 12         inc(tot);
 13         last[tot]:=y;
 14         next[tot]:=first[x];
 15         first[x]:=tot;
 16         num[tot]:=z;
 17         fa[y]:=x;
 18 end;
 19 
 20 function max(x,y:longint):longint;
 21 begin
 22         if x>y then exit(x);
 23         exit(y);
 24 end;
 25 
 26 function min(x,y:longint):longint;
 27 begin
 28         if x<y then exit(x);
 29         exit(y);
 30 end;
 31 
 32 procedure dfs(x:longint);
 33 var
 34         i,j,k,l,v:longint;
 35 begin
 36         if first[x]=0 then
 37           begin
 38             max1[x]:=min(lim[x],m div gold[x]);
 39             for i:=1 to max1[x] do
 40               begin
 41                 f[x,i,i*gold[x]]:=w[x]*i;
 42                 ans:=max(ans,f[x,i,i*gold[x]]);
 43               end;
 44             exit;
 45           end;
 46         max1[x]:=maxm;
 47         i:=first[x];
 48         while i<>0 do
 49           begin
 50             dfs(last[i]);
 51             max1[x]:=min(max1[x],max1[last[i]] div num[i]);
 52             inc(gold[x],num[i]*gold[last[i]]);
 53             i:=next[i];
 54           end;
 55         for i:=0 to max1[x] do
 56           begin
 57             l:=first[x];
 58             for j:=i*gold[x] to m do
 59               f[x,i,j]:=w[x]*i;
 60             l:=first[x];
 61             while l<>0 do
 62               begin
 63                 for j:=m downto i*gold[x] do
 64                   for k:=num[l]*i to max1[last[l]] do
 65                     for v:=(k-num[l]*i)*gold[last[l]] to j-i*gold[x] do
 66                       f[x,i,j]:=max(f[x,i,j],f[x,i,j-v]+f[last[l],k,v+num[l]*i*gold[last[l]]]-num[l]*i*w[last[l]]);
 67                 l:=next[l];
 68               end;
 69             for j:=i*gold[x] to m do
 70               ans:=max(ans,f[x,i,j]);
 71           end;
 72 end;
 73 
 74 procedure main;
 75 var
 76         i,j,k,x,y:longint;
 77         s:char;
 78 begin
 79         read(n,m);
 80         for i:=1 to n do
 81           begin
 82             read(w[i]);
 83             read(s,s);
 84             if s=B then read(gold[i],lim[i])
 85             else
 86               begin
 87                 read(k);
 88                 for j:=1 to k do
 89                   begin
 90                     read(x,y);
 91                     insert(i,x,y);
 92                   end;
 93               end;
 94           end;
 95         for i:=1 to n do
 96           if fa[i]=0 then dfs(i);
 97         writeln(ans);
 98 end;
 99 
100 begin
101         main;
102 end.
暴力
1                 for j:=m downto i*gold[x] do
2                   for k:=num[l]*i to max1[last[l]] do
3                     for v:=(k-num[l]*i)*gold[last[l]] to j-i*gold[x] do
4                       f[x,i,j]:=max(f[x,i,j],f[x,i,j-v]+f[last[l],k,v+num[l]*i*gold[last[l]]]-num[l]*i*w[last[l]]);

在这里,我们枚举的太多,其实只要满足k>=num[l]*i就行了

于是我们做完后可以对f数组做一些处理,使f数组的f[i,j,k]表示i物品买了j个以上,用了k元钱的最大力量

所以每次做完,我们都做一遍下面这个处理

1             for k:=max1[x] downto 1 do
2               for v:=gold[x]*k to m do
3                 up(f[x,k-1,v],f[x,k,v]);

只不过做完这个,我就想不出什么优化了,卡了好久,用cena自测总时间20s左右,BZOJ上就是过不了

过了好久,期间想过各种底层优化,可惜不懂,所以就没写了

然后发现一个很无语的优化,自测总时间6s多

对于每一个点,计算一下这颗子树最多用多少钱,记为lim[x],这样就不用每次都枚举到m了

  1 /**************************************************************
  2     Problem: 1017
  3     User: 1997cb
  4     Language: Pascal
  5     Result: Accepted
  6     Time:17432 ms
  7     Memory:42504 kb
  8 ****************************************************************/
  9  
 10 const
 11         maxn=52;
 12         maxm=2001;
 13 var
 14         w,gold,num,max1,fa,first,lim:array[0..maxn]of longint;
 15         next,last:array[0..maxn*2]of longint;
 16         f:array[0..maxn,0..101,0..maxm]of longint;
 17         n,m,ans,tot:longint;
 18  
 19 procedure insert(x,y,z:longint);
 20 begin
 21         inc(tot);
 22         last[tot]:=y;
 23         next[tot]:=first[x];
 24         first[x]:=tot;
 25         num[tot]:=z;
 26         fa[y]:=x;
 27 end;
 28  
 29 procedure up(var x:longint;y:longint);
 30 begin
 31     if x<y then x:=y;
 32 end;
 33  
 34 procedure down(var x:longint;y:longint);
 35 begin
 36     if x>y then x:=y;
 37 end;
 38  
 39 procedure dfs(x:longint);
 40 var
 41         i,j,k,l,v:longint;
 42 begin
 43         if first[x]=0 then
 44           begin
 45             down(max1[x],trunc(m/gold[x]));
 46             lim[x]:=max1[x]*gold[x];
 47             for i:=1 to max1[x] do
 48               f[x,i,i*gold[x]]:=w[x]*i;
 49             for k:=max1[x] downto 1 do
 50               for v:=gold[x]*k to m do
 51                 up(f[x,k-1,v],f[x,k,v]);
 52             exit;
 53           end;
 54         max1[x]:=maxm;
 55         i:=first[x];
 56         while i<>0 do
 57           begin
 58             dfs(last[i]);
 59             inc(lim[x],lim[last[i]]);
 60             down(max1[x],trunc(max1[last[i]]/num[i]));
 61             inc(gold[x],num[i]*gold[last[i]]);
 62             i:=next[i];
 63           end;
 64         down(lim[x],m);
 65         for i:=0 to max1[x] do
 66           begin
 67             l:=first[x];
 68             for j:=i*gold[x] to lim[x] do
 69               f[x,i,j]:=w[x]*i;
 70             l:=first[x];
 71             while l<>0 do
 72               begin
 73                 k:=num[l]*i;
 74                 for j:=lim[x] downto i*gold[x] do
 75                   for v:=0 to j-i*gold[x] do
 76                     up(f[x,i,j],f[x,i,j-v]+f[last[l],k,v+k*gold[last[l]]]-k*w[last[l]]);
 77                 l:=next[l];
 78               end;
 79             for k:=max1[x] downto 1 do
 80               for v:=gold[x]*k to lim[x] do
 81                 up(f[x,k-1,v],f[x,k,v]);
 82           end;
 83 end;
 84  
 85 procedure main;
 86 var
 87         i,j,k,x,y:longint;
 88         s:char;
 89 begin
 90         read(n,m);
 91         for i:=1 to n do
 92           begin
 93             read(w[i]);
 94             read(s,s);
 95             if s=B then read(gold[i],max1[i])
 96             else
 97               begin
 98                 read(k);
 99                 for j:=1 to k do
100                   begin
101                     read(x,y);
102                     insert(i,x,y);
103                   end;
104               end;
105           end;
106         for i:=1 to n do
107           if fa[i]=0 then
108           begin
109             dfs(i);
110             for j:=0 to max1[i] do
111               up(ans,f[i,j,lim[i]]);
112           end;
113         writeln(ans);
114 end;
115  
116 begin
117         main;
118 end.
最终版

1017: [JSOI2008]魔兽地图DotR - BZOJ,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。