zoj 3623 B – Battle Ships (完全背包?泛化背包?)

B – Battle Ships

Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Submit Status


Battle Ships is a new game which is similar to Star Craft. In this game, the enemy builds a defense tower, which has L longevity. The player has a military factory, which can produce N kinds of battle ships. The factory takes ti seconds to produce the i-th battle ship and this battle ship can make the tower loss li longevity every second when it has been produced. If the longevity of the tower lower than or equal to 0, the player wins. Notice that at each time, the factory can choose only one kind of battle ships to produce or do nothing. And producing more than one battle ships of the same kind is acceptable.

Your job is to find out the minimum time the player should spend to win the game.


There are multiple test cases. 
The first line of each case contains two integers N(1 ≤ N ≤ 30) and L(1 ≤ L ≤ 330), N is the number of the kinds of Battle Ships, L is the longevity of the Defense Tower. Then the following N lines, each line contains two integers i(1 ≤ i ≤ 20) and li(1 ≤ li ≤ 330) indicating the produce time and the lethality of the i-th kind Battle Ships.


Output one line for each test case. An integer indicating the minimum time the player should spend to win the game.

Sample Input

Sample Output

  1. 得到的经验是:如果不好直接表示造成伤害i所需要的最少时间,其实可以反过来,表示对于时间i造成的最大伤害。最后扫一遍就行了。
  2. 倒着考虑会好做很多。而可以这样做的原因是,每一个武器在建造之后输出的时候不会影响其他武器的建造,也就是每个武器是独立的       


View Code



Posted in ACM