一个有意思的小问题，不知道有没有人碰到过？

[lirijie1]

一个英雄打怪，途中有 n 个怪，怪物有两个属性攻击力 a[n]和价格 b[n]，英雄初始的攻击力为 0 但是金钱无限，如果英雄的攻击力小于怪物就得以怪物的价格收买作为自己军团的一员，反之则可以直接杀死怪物，收买的怪物战斗力可以叠加，问，通关最少用多少钱？

[yuchting]

算法盲人。。。排序 a 、 b 两个表，每次买 a 最高， b 最低的怪，打 b 最高， a 最低的怪，抛砖完毕

[shiznet]

怪物出现的顺序是可以自定的么？

[vB4h3r2AS7wOYkY0]

是不是我 2 了

最少用 b[n]

[loudis]

如果可以随便选怪，找到 a[n]最大值的怪物 i ，然后根据 a[n]/b[n] 性价比排名，再取前几个累加 a 大于 a[i]即可？

如果打怪顺序开始随机固定，就不好算了。。

[ppdg]

乍一看貌似是最小费用最大流问题

[glchaos]

金钱无限，为什么还要求最少用多少钱？

[songco]

感觉和背包算法思路接近.

[ibeta]

应该可以利用线性规划求解吧，可惜大学学的都还给老师了。
写了一个递归版的 demo ，在可杀可不杀时调用递归，计算所有可能的花费，不过太多就栈溢出了╯□╰
http://jsfiddle.net/ibeta/8dc1o0p1/

[Axurez]

途中有 n 个怪，怎么感觉怪的顺序是确定的。。。

[a154312237]

题目的意思没弄清
1.怪物顺序已经确定 自己攻击力大于怪物的时候可以选择打死或是收买
2.攻击力大于怪物的时候必须打死 怪物顺序自己安排
是哪一个啊

[lzdhlsc]

钱 d[i]
战斗力 s[i]
for i in xrange(n):

d[i] = min(d[j] if s[j] >= a[i] else d[j] + b[i])

[lzdhlsc]

@lzdhlsc 发错了 请无视

[hellov22ex]

b2 ？

其实我觉得这个和具体钱数有关系

如果 b1 b2 b3 就是 1 2 3 的话，买了 2 的开始就能吊打了

但是如果是 1 2 4 的话，还要继续买

这玩意咋算？楼主有答案了 @我下

[lksltjw]

数据规模？
时间限制？
空间限制？
算法题出得这么不专业。。。

[lirijie1]

@ppdg 我也不晓得，这个是朋友碰到的，他说原题就是这样，没有别的条件了

[linhua]

@yuchting @lirijie1
题目是“通关最少用多少钱？”，因此怪物出现顺序是理想的。如果怪物出现顺序确定的话。这题也就没意义了。
1.买 a 最高， b 最低的怪，这是最理想的情况。
2.如果 a 最高的怪， b 不是最低。那么通关最少用的钱数是不大于这个 b 的。因为直接买这个怪，肯定能通关。
因此先按 b 对怪进行排序，从小到大。
如果” a 最高的怪“位于第 1 或第 2 ，那毫无疑问，通关最少用的钱数就是 b[1],b[2]了。
若“ a 最高的怪”位于第 3 ，则需对第 1 和第 2 的怪的属性进行相加，比较相加的值和“ a 最高的怪”的属性值，若相加的值 a 较大，且 b 较小，就选相加的那一组合。否则选“ a 最高的怪”。
若“ a 最高的怪”位于第 4 ，则依次计算 b[1]+b[2],b[1]+b[3],b[2]+b[3],b[1]+b[2]+b[3]，直到遇到 a 较“ a 最高的怪”大，且 b 较小为止，这时选对应的组合。或者直到遇到 b 较“ a 最高的怪”大为止，这时选“ a 最高的怪”。遍历完后还没有满足条件的，就选“ a 最高的怪”。
。。。。。。。。。。。