Добрый вечер!
Не могу решить задачу K с этого контеста. После прочтения разбора все равно не понял.
Условие:
Вася готовит N шашлыков. В каждом шашлыке qi кусочков. Вася тратит 1 секунду, чтобы наколоть 1 кусок мяса. Когда он заканчивает накалывать i-ый шашлык, он сразу же приступает к (i+1)-ому.
Вася часто мечтает. Каждая мечта занимает ровно 1 секунду и он забывает наколоть кусочек мяса в эту секунду. Вася не мечтает два раза в любые последовательные (t+1) секунды.
Из-за того, что он мечтает, некоторые шашлыки могут быть не полные. Однако гости не будут злиться, если i-ый шашлык имеет не менее xi кусочков.
Требуется посчитать, сколькими способами может Вася мечтать в течении его работы, чтобы все посетители были довольны. Ответ вывести по модулю 10^9+7.
Ограничения:
1 <= N <= 1000, 0 <= t <= 100, 1 <= qi <= 250, 0 <= xi <= qi
Пронумеруем все кусочки в сквозном порядке.
Я считал динамику
d[n][k], гдеn— номер кусочка, который относится к шашлыкуj, аk— количество забытых кусочков для шашлыкаj.jлегко рассчитывается поn.Динамику разворачивал вперед. Из каждого состояния возможно всего 2 перехода: пусть
next = n + t— следующий кусочек, который мы можем забыть, если забудем кусочекn.Итак, если мы забываем текущий кусочек, делаем один из следующих переходов
если
nextпринадлежит шашлыкуjиk < q_i - x_iобновляемd[next][j+1]если
nextне принадлежит шашлыкуjобновляемd[next][1]— забудем один кусочек уже в другом шашлыкеj' > j.Переходы для незабывания тривиальны
next = n + 1:если
nextпринадлежит шашлыкуjобновляемd[next][j]если
nextне принадлежит шашлыкуjобновляемd[next][0]— начинаем новый шашлык, в котором ещё ничего не забыли.Осталось только аккуратно проинициализировать начальные состояния динамики. После решения думаю, что в данном случае удобнее было бы решать в обратную сторону.
спасибо, зашла такая динамика :)
единственное что,
next = i + t + 1иk <= q_i - x_iи там, наверно опечатка: "если
nextпринадлежит шашлыкуjобновляемd[next][j]" должно быть обновляемd [next][k]