Не знаю, как правильно решить следующую задачу. Есть идеи, но они не проходят. Кто знает, направьте в верное русло, пожалуйста. Также, если знаете похожие задачи, то поделитесь ссылками на них. Оригинальная формулировка задачи с тестами доступна [здесь](https://yadi.sk/i/Z8_wStsR3VTmJs)↵
↵
Во входном файле до 50 тестов. Каждый тест — отдельная подзадача. Нужно вывести ответ для каждой подзадачи с новой строки. Подзадача состоит в следующем:↵
↵
На нашем пути есть от 1 до 20 засад, в каждой засаде сидят $ k[i] $ разбойников (от 1 до 1000), чтобы они нас пропустили, нужно $ c[i] $ монет (от 1 до 1000). Изначально в нашем отряде 0 наемников.↵
↵
Мы можем:↵
↵
1. Нанять бандитов, сидящих в засаде, потратив $ 2*c[i] $ монет↵
↵
2. Заплатить бандитам $ c[i] $ монет, чтобы они нас пропустили↵
↵
3. Сразиться с ними. Погибает одинаковое количество с обеих сторон. Причем у нас те наемники, которые были наняты раньше, погибают первыми. Но наемники не выдерживают больше трех битв. После третьей битвы они уходят от нас, если выживают.↵
↵
Необходимо проехать все засады, потратив наименьшую сумму денег. В ответ выдать эту сумму денег.↵
↵
Ограничения: 3 секунды, 256 МБ на тест, таким образом, 0.06 секунд и 256 МБ на одну подзадачу.↵
↵
Думал в сторону двумерного ДП. Параметры:↵
↵
* количество пройденных засад↵
↵
* набранная сумма↵
↵
Для состояния $ dp[k][sum] $ хранить оптимальную тройку $ (n1, n2, n3) $ — сколько наемников могут участвовать в одной битве, двух и трех соответственно. Для недостижимых позиций $ (-1, -1, -1) $. Но не ясно, как выбирать из двух возможных троек лучшую при одинаковых переходах. Если выбирать по сумме, то тройка $(1000, 0, 0)$ окажется лучше тройки $(0, 0, 999)$. но все наемники убегут после первой битвы. Если выбирать по компонентам, то $(0, 0, 2)$, окажется лучше, чем $(999, 0, 1)$, но тогда не победить 1000 разбойников. Поэтому вариант с тройками не проходит, а больше адекватных идей нет.
↵
Во входном файле до 50 тестов. Каждый тест — отдельная подзадача. Нужно вывести ответ для каждой подзадачи с новой строки. Подзадача состоит в следующем:↵
↵
На нашем пути есть от 1 до 20 засад, в каждой засаде сидят $ k[i] $ разбойников (от 1 до 1000), чтобы они нас пропустили, нужно $ c[i] $ монет (от 1 до 1000). Изначально в нашем отряде 0 наемников.↵
↵
Мы можем:↵
↵
1. Нанять бандитов, сидящих в засаде, потратив $ 2*c[i] $ монет↵
↵
2. Заплатить бандитам $ c[i] $ монет, чтобы они нас пропустили↵
↵
3. Сразиться с ними. Погибает одинаковое количество с обеих сторон. Причем у нас те наемники, которые были наняты раньше, погибают первыми. Но наемники не выдерживают больше трех битв. После третьей битвы они уходят от нас, если выживают.↵
↵
Необходимо проехать все засады, потратив наименьшую сумму денег. В ответ выдать эту сумму денег.↵
↵
Ограничения: 3 секунды, 256 МБ на тест, таким образом, 0.06 секунд и 256 МБ на одну подзадачу.↵
↵
Думал в сторону двумерного ДП. Параметры:↵
↵
* количество пройденных засад↵
↵
* набранная сумма↵
↵
Для состояния $ dp[k][sum] $ хранить оптимальную тройку $ (n1, n2, n3) $ — сколько наемников могут участвовать в одной битве, двух и трех соответственно. Для недостижимых позиций $ (-1, -1, -1) $. Но не ясно, как выбирать из двух возможных троек лучшую при одинаковых переходах. Если выбирать по сумме, то тройка $(1000, 0, 0)$ окажется лучше тройки $(0, 0, 999)$. но все наемники убегут после первой битвы. Если выбирать по компонентам, то $(0, 0, 2)$, окажется лучше, чем $(999, 0, 1)$, но тогда не победить 1000 разбойников. Поэтому вариант с тройками не проходит, а больше адекватных идей нет.
