↵
↵
На нашем пути есть от 1 до 20 засад, в каждой засаде сидят $ k[i] $ разбойников (от 1 до 1000), чтобы они нас пропустили, нужно $ c[i] $ монет (от
↵
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
↵
Мы можем:↵
↵
1. Нанять бандитов, сидящих в засаде, потратив $ 2*c[i] $ монет↵
↵
2. Заплатить бандитам $ c[i] $ монет, чтобы они нас пропустили↵
↵
3. Сразиться с ними. Погибает одинаковое количество с обеих сторон. Причем у нас те наемники, которые были наняты раньше, погибают первыми. Но наемники не выдерживают больше трех битв. После третьей битвы они уходят от нас, если выживают.↵
↵
Необходимо проехать все засады, потратив наименьшую сумму денег. В ответ выдать эту сумму денег.↵
↵
Ограничения: 3 секунды, 256 МБ на тест, таким образом, 0.06 секунд и 256 МБ на одну подзадачу.↵
↵
Думал в сторону двумерного ДП. Параметры:↵
↵
* количество пройденных засад↵
↵
* набранная сумма↵
↵
Для состояния $ dp[k][sum] $ хранить оптимальную тройку
↵
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 $
↵
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,
↵
I ask you to help finish this problem to the end and, if possible, provide links to similar problems.
