Здравствуйте! При решении задач на динамику я натолкнулся на две, которые не могу решать привычным для меня подходом к ней. Во всех материалах по дп, которые я видел либо показаны готовые решения известных задач, либо разбираются самые основные его принципы, поэтому я решил написать сюда.

В первой надо найти число способов наградить 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], но я не представляю, как это делать.