Не знаю, как правильно решить следующую задачу. Есть идеи, но они не проходят. Кто знает, направьте в верное русло, пожалуйста. Также, если знаете похожие задачи, то поделитесь ссылками на них. Оригинальная формулировка задачи с тестами доступна здесь
Во входном файле до 50 тестов. Каждый тест — отдельная подзадача. Нужно вывести ответ для каждой подзадачи с новой строки. Подзадача состоит в следующем:
На нашем пути есть от 1 до 20 засад, в каждой засаде сидят k[i] разбойников (от 1 до 1000), чтобы они нас пропустили, нужно c[i] монет (от 1 до 1000). Изначально в нашем отряде 0 наемников.
Мы можем:
Нанять бандитов, сидящих в засаде, потратив 2 * c[i] монет
Заплатить бандитам c[i] монет, чтобы они нас пропустили
Сразиться с ними. Погибает одинаковое количество с обеих сторон. Причем у нас те наемники, которые были наняты раньше, погибают первыми. Но наемники не выдерживают больше трех битв. После третьей битвы они уходят от нас, если выживают.
Необходимо проехать все засады, потратив наименьшую сумму денег. В ответ выдать эту сумму денег.
Ограничения: 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 разбойников. Поэтому вариант с тройками не проходит, а больше адекватных идей нет.
