注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

1017: [JSOI2008]魔兽地图DotR  

2013-01-02 20:33:45|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

HINT

Source


这题是很久以前做的,当时被题目坑了……以为是个DAG……结果发现这句话“装备的合成路线可以用一棵树来表示。”有巨大歧义……其实把需要的低级装备看成儿子,就是棵树了啊囧……
f[编号][钱][个数]的做法就不说了,前人之述备矣。
我当时自己写,结果WA掉了,于是找当时用时排名第一的treeboy_要代码,发现原来这题是有只记编号和钱的做法的啊!!
为什么我现在才写题解?当时虽然A了但理解不是很透彻。今天终于彻底弄懂了。

首先我们找到根,然后dfs下去计算信息。
money[v] :搞到一个这个装备v所用的钱。
maxsum[v] :最多能搞到几个装备v。
B装备的已经知道了,A装备的通过儿子们算出来就行。

考虑一个装备v,假设它最多只能取s个,这棵子树最多只能用掉m块钱,那么如果已知买v的个数i,用掉的钱就会分成两半:
part 1. i * money[v]  即买 i 个 v用的钱。
part 2. 对于每个儿子u,无回报制造i * needSum[u]个u后,以u为根的子树上花的钱。(无回报制造就是不算这家伙产生的能量)
记best[v][i][j]表示这种情况下买i个v,花j块钱的最优值。

part 1很好计算,i * money[v]块钱,产生了i * energy[v]的能量。
part 2呢?也就是说现在v固定了,j 固定了,要合理安排这 j 块钱,使得儿子们能产生的能量最大。

先来看对背包的另一种理解。若f是个数组,g是个数组,定义:
(f merge g)[n] = max{ f[i] + g[n - i] }  (0 <= i <= n)
其中merge是个二元运算。f merge g的结果是一个数组。

实际意义是:
f[i]表示通过方式 f 正好花i块钱能获得的最大价值,g[i]表示通过方式 g 正好花i块钱的最大价值
(f merge g)[i]表示通过f、g两种方式,正好花i块钱能获得的最大价值。

容易验证以下性质:
交换律:a merge b = b merge a
结合律:(a merge b) merge c = a merge (b merge c)

现在回到刚才的问题,计算part 2。
发现用merge算子就很好理解了。
现在我们的任务就是计算出来opt[u][i][j],表示无回报制造i * needSum[u]个u后,花j块钱能获得的最大价值。
然后假设v的儿子分别为u1, u2, ..., uk, 那么part 2最优值就是
(opt[u1][i][j] merge opt[u2][i][j] merge ... merge opt[uk][i][j])这个数组中下标为0, 1, ..., m中的最大值。

所以实际上我们要关注的是opt[u][i][j]怎么求。
如果我们以i递增的顺序依次处理opt[u][*][j]就会发现这是个坑。因为i递增,u的无回报制造量是递增的,最多的有回报制造量是递减的……而merge是很难有逆运算的……
所以考虑递减处理,即依次处理opt[u][s][j], opt[u][s - 1][j], ..., opt[u][0][j]。
这样一来每次从i变为i - 1,我们就多了needSum[u]个u可以有回报制造。

于是可以定义g[u],表示最多只能制造1个u,如果u有个儿子叫没头脑,那么没头脑最多只能制造needSum[没头脑]个,如果没头脑有个儿子叫不高兴,那么不高兴最多只能制造needSum[没头脑] * needSum[不高兴],如果不高兴有个儿子叫大头娃娃,那么大头娃娃最多只能制造needSum[没头脑] * needSum[不高兴] * needSum[大头娃娃]……依次类推。
如果定义符号
f merge^ k = f merge f merge ... merge f (k个f)。
那么容易知道:
opt[u][i - 1] = opt[u][i] merge (g[u] merge^ needSum[u])

也就是说当i - 1了,可以去算:
  opt[u1][i - 1] merge opt[u2][i - 1] merge ... merge opt[uk][i - 1]
= (opt[u1][i] merge (g[u1] merge^ needSum[u1])) merge (opt[u2][i] merge (g[u2] merge^ needSum[u2])) merge ... merge (opt[uk][i] merge (g[uk] merge^ needSum[uk]))
= (opt[u1][i] merge opt[u2][i] merge ... merge opt[uk][i]) merge ((g[u1] merge^ needSum[u1]) merge (g[u2] merge^ needSum[u2]) merge ... (g[uk] merge^ needSum[uk]))

在计算所有best之前,可以先求出
allG[v] = (g[u1] merge^ needSum[u1]) merge (g[u2] merge^ needSum[u2]) merge ... (g[uk] merge^ needSum[uk])。
这样就能通过一次merge操作知道best[v][i - 1]了。

好像漏掉了什么?
我们不知道opt[u][s]的值。
1017: [JSOI2008]魔兽地图DotR - vfleaking - vfleaking的博客

由此一来我们的任务只剩下两个:
1. opt[u][s]的求法。
2. g[u]的求法。

发现这两个东西是可以树形DP的。

计算su[u] = maxSum[v],其中v是u的父亲。

于是就是要求opt[v][su[v]]。
记f[v] = opt[v][su[v]]
发现什么了么……这家伙跟我们刚才讨论了半天的best实际上是一个问题……

1017: [JSOI2008]魔兽地图DotR - vfleaking - vfleaking的博客
 
f[v]跟best一样,是可以根据f[u], g[u]来求出来的。
不过我们求出非root的best是毫无意义的……

那么如何求g[v]?
我汗,几乎就是allG[v]吧。
首先g[v] = allG[v]。
考虑一下v取几个。
由于要么取0个,要么取1个,但是你取了1个,你整棵子树都不能取其他物品了。
所以直接用energy[v]去更新g[v][money[v]]。
就完事了。

好……那么现在我们能得到root的所有孩子的f、g,于是就能算出root的best了。
……但是发现这样做非常sb。
因为root没有父亲……于是我们规定su[root] = 0……
所以best[root] = f[root]……
不用再求best了……

各种dp的转移见我的代码。刚才基本已经说完了。

主要代码:

112 void dfs(int idx, int sum)
113 {
114     equipment *cur = &e[idx];
115     for (int i = 0i < e[idx].nNeedi++)
116         dfs(cur->needIndex[i], cur->maxsum * cur->needSum[i]);
117 
118     int *curF = f[idx], *curG = g[idx];
119     static int h[MaxM + 1];
120     fill(h, h + m + 1, 0);
121     for (int i = 0 ; i < cur->nNeedi++)
122     {
123         relaxDP(h, f[cur->needIndex[i]]);
124 
125         for (int j = 0j < cur->needSum[i]; j++)
126             if (!relaxDP(curG, g[cur->needIndex[i]]))
127                 break;
128     }
129 
130     bool updated = true;
131     for (int i = cur->maxsum - sumi >= 0i--)
132     {
133         int moneyi = cur->money * i, energyi = cur->energy * i;
134         for (int j = moneyij <= mj++)
135             relax(curF[j], h[j - moneyi] + energyi);
136 
137         if (updated)
138             updated = relaxDP(h, curG);
139     }
140 
141     if (cur->money <= m)
142         relax(curG[cur->money], cur->energy);
143 }

所谓relax和tension:

051 template <class T>
052 inline bool tension(T &a, const T &b)
053 {
054     if (b < a)
055     {
056         a = b;
057         return true;
058     }
059     return false;
060 }
061 template <class T>
062 inline bool relax(T &a, const T &b)
063 {
064     if (b > a)
065     {
066         a = b;
067         return true;
068     }
069     return false;
070 }

所谓relaxDP:(这是加了些优化的版本)

090 inline bool relaxDP(int *a, int *b)
091 {
092     bool updated = false;
093     
094     for (int i = m - 1i >= 0i--)
095         if (a[i] > 0 || i == 0)
096             for (int j = 1i + j <= mj++)
097                 if (b[j] > 0 && relax(a[i + j], a[i] + b[j]))
098                     updated = true;
099 
100     int maxV = 0;
101     for (int i = 0i <= mi++)
102     {
103         if (a[i] <= maxV)
104             a[i] = 0;
105         else
106             maxV = a[i];
107     }
108 
109     return updated;
110 }

完整代码:
  评论这张
 
阅读(2969)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017