Здравствуйте! Помогите решить задачу на ДП. Какая должна быть динамика,переходы?
Спасибо за внимание!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
4 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
8 | Dominater069 | 154 |
8 | nor | 154 |
Здравствуйте! Помогите решить задачу на ДП. Какая должна быть динамика,переходы?
Спасибо за внимание!
Название |
---|
У меня есть такая идея: пусть у нас 8 гирек, тогда можно перебрать все маски вида: 00000000, 00000001 и т.д. То что нули это гирьки, которыми мы хотим решить задачу для первых двух кучек(т.е проверяем можем ли набрать этими гирями две кучки с одинаковым весом(просто перебор бит масок, если да, то запомнить все варианты с различными весами). Всё что 1 это гирьки, которыми набираем две последние кучки. Решаем как и для первых двух, затем смотрим, есть ли совпадения по весам. Сдавать не пробовал, так что в правильности не уверен.
за O(2^N * N^2) ?
в классическом решении такой задачи общая схема динамики такая:
можно ли набрать i в первой кучке, j — во второй, k — в третьей. размерность динамики = количество куч — 1. (в последней всегда столько, сколько остаётся).
для данной задачи вам понадобится ~ 10^8 памяти. не очень хорошо.
Если вы заглянете в вопросы, то увидите, что автор предполагал перебор.
ну и переходы, наверное, так. берете последовательно все гирьки. для каждой перебираете все состояния вашей динамики. допустим, вес текущей = r. тогда если dp[i][j][k] = true, то dp[i+r][j][k], dp[i][j+r][k], dp[i][j][k+r] = true. динамика, конечно, "с просмотром назад".
Что значит "с просмотром назад"?
Можно написать такую динамику:
dp[i][mask][sum] — существует ли у маски mask из первых i гирек подмножество с суммой sum.
Переходы:
dp[i + 1][mask][sum] = true — не берём текущую гирьку в маску
dp[i + 1][mask|2i][sum] = true — берём гирьку в маску, но не берём в сумму
dp[i + 1][mask|2i][sum + m[i]] = true — берём гирьку в маску и в сумму.
Чтобы сэкономить память, будем хранить только динамику для предыдущего i.
Восстановление ответа понятно.
UPD: это заходит за 0.15, так что тоже имеет право на существование :)
Ограничение в 14 говорит нам "решайте за 3^N перебором подмасок маски".
Действительно, можно решать так, но можно это сделать еще лучше — у задачи есть классическое решение за N*2^N.
Посчитаем необходимый вес кучки. Если это нецелое число, то очевидно, что дела наши плохи) Далее задачу можно переформулировать так — можно ли разбить гирьки на 2 кучки, каждая из которых состоит из 2 кучек весом х?
Для каждой маски находим ее вес. Будем говорить, что маска хорошая, если ее вес х. Будем говорить, что маска очень хорошая, если у нее есть хорошая подмаска — для такой маски дополнительно будем хранить, какая именно ее подмаска является хорошей. Будем говорить, что маска вообще классная, если она очень хорошая и при этом ее вес 2*х. Все это считается очевидным способом за N*2^N, рассматривая маски от меньших к большим.
Очевидное наблюдение — любая вообще классная маска может быть разложена на 2 кучки веса х. В одну возьмем ее хорошую подмаску, в другую — то, что осталось.
Теперь для решения изначальной задачи перебираем все возможные подмаски гирек, если подмаска вообще классная, и ее дополнение до полной маски — тоже, то мы нашли ответ. Очевидно, что он имеет вид: хорошая подмаска маски + остаток маски + хорошая подмаска дополнения + остаток дополнения.
Если ничего не нашли, то No nolution.
Я сабмитнул, работает за 0.005.