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](https://yadi.sk/i/Z8_wStsR3VTmJs).↵
↵
On our way we will meet several groups of bandits (from 1 to 20). Each group has two parameters:↵
↵
1. $ size[i] $ — number of bandits (from 1 to 1000)↵
2. $ cost[i] $ — cost we have to pay them if we do not want to have problems (from 1 to 1000)↵
↵
We can:↵
↵
1. Pay them $ cost[i] $ to pass them↵
↵
2. Pay them $ 2 * cost[i] $ to hire them↵
↵
3. 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:↵
↵
1. $ k $ — Number of passed groups.↵
↵
2. $ 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.
↵
On our way we will meet several groups of bandits (from 1 to 20). Each group has two parameters:↵
↵
1. $ size[i] $ — number of bandits (from 1 to 1000)↵
2. $ cost[i] $ — cost we have to pay them if we do not want to have problems (from 1 to 1000)↵
↵
We can:↵
↵
1. Pay them $ cost[i] $ to pass them↵
↵
2. Pay them $ 2 * cost[i] $ to hire them↵
↵
3. 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:↵
↵
1. $ k $ — Number of passed groups.↵
↵
2. $ 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.
