Здравствуйте! При решении задач на динамику я натолкнулся на две, которые не могу решать привычным для меня подходом к ней. Во всех материалах по дп, которые я видел либо показаны готовые решения известных задач, либо разбираются самые основные его принципы, поэтому я решил написать сюда.
В первой надо найти число способов наградить k работников из n так, чтобы никакие два награжденных не стояли подряд по простому модулю. Очевидное разбиение на подзадачи d[i][j] – ответ для i работников, из которых j надо наградить. d[0][0]=d[i>0][0]=1; d[0][j>0]=0
Из k выбранных одного мы наградим первым => ответ можно разбить на независимые множества, по его номеру. Что-то вроде цикла по t от 0 до i по всем номерам. d[i][j]+=d[max(i-t-2,0)][j-1]
Проблема в том, что 1<=n,m<=10^5. Т.е. если по памяти еще можно оптимизировать, раз нам не нужны значения d[i][j-p] для вычисления d[i][j] если p>1, то по времени квадрат не проходит. Можно ли разбить на подзадачи более эффективно, или надо искать формулу?
Во второй определена функция g от последовательности чисел, которая возвращает натуральное число, равное длине максимальной подстроки из одинаковых чисел, или любой из них, если таких много. Надо найти сумму g по всем таким последовательностям, если на одной позиции могут стоять целые числа на интервале [1;c]. Само условие: http://tinyurl.com/lzkhbmn
Я написал решение за куб, который хотя бы не получает WA. Можно посмотреть здесь: http://pastebin.com/LPW2JDzH
Моя идея — найти d[pos][len].total как количество последовательностей длины pos, в которых не более len одинаковых символов стоят подряд, а d[pos][len].num не более len, и не менее len. Потом можно посчитать сумму всех d[n][j].
Пусть на позиции pos мы хотим поставить i одинаковых чисел справа. i принадлежит промежутку [1;lim]. (lim выбирается так, чтобы не превосходить len, и чтобы не создавать последовательностей длины больше n) Тогда из нулевой позиции мы можем сделать это c способами, а из ненулевой только c-1 м (Т.к. мы не можем ставить то же число, что и на позиции pos).
d[pos+i][len].num обновляется, когда мы ставим после num текущих любые числа, или когда ставим ровно len чисел.
Но из-за того, что внутри циклов достаточно дорогие операции, код падает с TL. Т.к. динамики с разными len получились независимыми, можно искать выражение d[pos][n] через d[pos-1][n], но я не представляю, как это делать.
В первой, кажется, можно считать динамику только для n равных степеням двойки, ну и еще помнить, взяли ли мы первого и последнего человека. Тогда можно "собрать" ответ для n, сделав O(log(n)) объединений.
А как сделать динамику для степеней двойки?
Ниже привели формулу, но динамика для степеней двойки с объединением, это все равно очень интересно. Можете дать ссылку на задачи, где она используется?
В этой задаче это все таки не подходит, тут объединение за квадрат делается. Можно конечно соптимизировать его до n log n, но такое решение скорее всего затлится.
По поводу степеней двоек, помню только задачу L с этого контеста. На том контесте, кстати, есть еще несколько неочевидных динамик.
Первая решается без динамики. Есть несложная биекция между способами выбрать k из n без повторений, не выбрав два подряд, и способами выбрать k из n-k+1 без повторений. Значит, ответ Cn - k + 1k, который можно посчитать, разделив один факториал на два других по модулю (по простому модулю это особенно просто).
Вторая наверно решается так. Пусть g(m) — количество последовательностей длины n, в которых не встречается более m одинаковых чисел подряд. Если мы найдем все g(m), дальше все ясно. Осталось только их найти. Зафиксируем m. Пусть di — количество последовательностей длины i, в которых не встречается более m одинаковых чисел подряд. Их можно пересчитывать примерно так:
(на самом деле нужно еще учесть случай j = 0 как описано в посте). Такую сумму можно находить за O(1), если иметь массив частичных сумм для d или просто двигать окно. Наверно можно даже записать проще: di = di - 1 - (c - 1)di - m - 1 + (c - 1)di - 1 (случай i < m + 1 надо тоже как-нибудь учесть).
Вроде понятно, спасибо)
Случайно нажал случайно на минус вместо плюса. Извиянюсь.