首页 > ACM题库 > HDU-杭电 > HDU 4257-CosmoCraft-贪心-[解题报告]HOJ
2015
05-23

HDU 4257-CosmoCraft-贪心-[解题报告]HOJ

CosmoCraft

问题描述 :

In the two-player game CosmoCraft you manage an economy in the hopes of producing an army capable of defeating your opponent. You manage the construction of workers, production facilities, and army units; the game revolves around balancing the resources you allocate to each. The game progresses in turns.
1. Workers give you income at the rate of 1 dollar per turn.
2. Production facilities let you produce either an army unit or a worker for the cost of 1 dollar. (only 1 army unit or worker can be produced per turn per facility)
3. It costs 1 dollar to create a production facility.
4. Your army, of course, lets you fight against your opponent.
You start off with n workers and k production facilities. The game progresses in turns �C at each turn, you can spend the income you get from your workers on a mixture of workers, army, and creating production facilities. Workers produced this round do not give you income until the next round; likewise, production facilities do not become active until the next round. Any unspent income from the current round carries over to the next.
At the end of a round, you can take the total army you’ve produced and attack your opponent; if you have strictly more units than your opponent, the opponent loses immediately, and you retain the difference of the army sizes. Otherwise, your army is crushed and your opponent is left with the difference of the army sizes. (it would be wise for him to counter-attack after this, but you don’t lose immediately at least). The game ends after t turns, at which point both players will usually attack with the larger army reigning victorious.
You’re playing against your friend, and since you’ve played against him so many times you know exactly what he’s going to spend his money on at every turn, and exactly when he’s going to attack. Knowing this, you’ve decided that the best strategy is to play defensively �C you just want to survive every attack, and amass as large an army in the meantime so you can counterattack (and hopefully win) at the end of the game.
What’s the largest army you can have at the end of the game, given that you must survive all your friend’s attacks?

输入:

There will be several test cases in the input. Each test case will begin with a line with three integers:
n k t
where n (1≤n≤100) is the number of workers you start with, k (1≤k≤100) is the number of production facilities you have at the start, and t (1≤t≤10,000) is the number of turns. On the next line will be t-1 integers, ai (0≤ai≤Max signed 64-bit integer), separated by single spaces. The ith integer indicates the strength of the attack (that is, the number of army units your opponent is using in that attack) on turn i. The input will end with a line with three 0s.
Hint

Huge input, please ues c++.

输出:

There will be several test cases in the input. Each test case will begin with a line with three integers:
n k t
where n (1≤n≤100) is the number of workers you start with, k (1≤k≤100) is the number of production facilities you have at the start, and t (1≤t≤10,000) is the number of turns. On the next line will be t-1 integers, ai (0≤ai≤Max signed 64-bit integer), separated by single spaces. The ith integer indicates the strength of the attack (that is, the number of army units your opponent is using in that attack) on turn i. The input will end with a line with three 0s.
Hint

Huge input, please ues c++.

样例输入:

8 4 6
22 6 10 14 0
4 3 3
0 0
6 9 7
0 0 11 0 7 0
0 0 0

样例输出:

-1
11
101

  这道题今天做了好长时间,不清楚该如何贪心,想了好久。后来想的差不多了,开始写,但是连测试样例都出不来。网上找博客看,发现如果某一轮的士兵人数不足以抵挡对手的侵略,需要把工人转换成士兵。这个。。我压根从题目里面就没有读出来,后来想了有半个小时左右的时间,大概感觉是这个题目里面说的那个production facilities 这个神物的所作所为吧。哎,对于不玩那个dota,魔兽之类的游戏的孩子伤不起啊。

  贴个链接:http://hi.baidu.com/littletobbies/item/b33fa10ab0694c303b53ee76

参考:http://www.cnblogs.com/RainingDays/archive/2012/12/28/2837574.html