Hello, codeforces! I do not know how to solve this DP problem, so I really want to know how. I will explain the condition of this problem briefly. Link on original pdf with examples.
On our way we will meet several groups of bandits (from 1 to 20). Each group has two parameters:
- size[i] — number of bandits (from 1 to 1000)
- cost[i] — cost we have to pay them if we do not want to have problems (from 1 to 1000)
We can:
Pay them cost[i] to pass them
Pay them 2 * cost[i] to hire them
Fight them. In this case we will lose size[i] hired soldiers. The first to die are those who had been hired earlier. The hired mercenaries leave our squad after participating in three battles.
You need to go all the way, having spent the least amount of money. Answer — this amount. At the initial time in our squad there are no soldiers.
The input file contains from 1 to 50 tests. On each input file, time limit — 3 sec, memory limit — 256 MB. Therefore, for one test — 0.06 sec. Tests can be different, numbers cost[i] and size[i] can be different.
I tried to apply two-dimensional dynamic programming:
k — Number of passed groups.
sum — The amount of money spent
The cell dp[k][sum] contains the best triple of the mercenaries (n1, n2, n3), who can fight in one battle, two and three battles. But I can not understand how to choose the best triple among all the transitions.
If we use sum of components, triple (1000, 0, 0) will be better, then (0, 0, 999), but after battle with size[i] = 1 we get (0, 0, 0) from first and (0, 998, 0) from second triple and second will be better.
If we use lexicographic order, triple (0, 0, 1) will be better, then (1000, 0, 0), but first triple can not win in battle with size[i] = 1000 bandits.
I ask you to help finish this problem to the end and, if possible, provide links to similar problems.
