Оптимизации динамического программирования

Во всех заданиях необходимо вывести остаток от деления количества искомых последовательностей на число \(10^9+7\).

В некоторых задачах установлено небольшое ограничение по памяти (8MiB). В этих задачах нужно написать решение, не хранящее все вычисленные значения функции динамического программирования. Необходимо хранить только последний вычисленный слой и новый слой значений функции, то есть вместо (например) двумерного массива нужно хранить два одномерных массива, в которых будут храниться значения функции для \(n=i\) и вычисляться новые значения функции для \(n = i + 1\). Это можно сделать используя два вектора и меняя их значения местами при помощи функции swap.

В случае превышения лимита по памяти решение может получать статус «Ошибка исполнения» на тесте.

A: Разбиения на слагаемые

По данному числу \(n\), \(1\le n\le 5000\), определите количество разбиений числа \(n\) на натуральные слагаемые.

Предполагается решение сложности \(O(n^2)\).

5

7

B: Последовательности длины \(n\) с суммой \(s\)

По данными числам \(n\) и \(s\), \(1\le n\le 5000\), \(1\le s \le 5000\), определите количество последовательностей из \(n\) натуральных чисел, сумма элементов которых равна \(s\).

Предполагается решение сложности \(O(ns)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(s)\) памяти.

3 5

6

C: Пилообразные последовательности

Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам \(n\) и \(k\), \(1\le n\le 5000\), \(2\le k \le 5000\), определите число пилообразных последовательностей длины \(n\), составленных из чисел 1..\(k\).

Предполагается решение сложности \(O(nk)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(k)\) памяти.

3 3

10

D: Разбиения на \(k\) слагаемых

По данным числам \(n\) и \(k\), \(1\le n\le 400\), \(1\le k\le 400\), определите количество разбиений числа \(n\) на \(k\) натуральных слагаемых.

Предполагается решение сложности \(O(n^2k)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(n^2)\) памяти.

6 3

3

E: Пилообразные перестановки

По данному значению \(n\), \(1\le n\le 5000\), определите количество пилообразных перестановок из \(n\) элементов.

Предполагается решение сложности \(O(n^2)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(n)\) памяти.

3

4

F: Двоичные последовательности, не содержащие \(k\) единиц подряд

По данными числам \(n\) и \(k\), \(1\le n\le 10^7\), \(1\le k \le 10^7\), определите количество двоичных последовательностей длины \(n\), не содержащих \(k\) единиц подряд.

Предполагается решение сложности \(O(n)\).

3 3

7

G: Плавные последовательности — 2

Рассмотрим последовательность из \(n\) элементов, составленную из чисел от \(1\) до \(k\). Назовём последовательность плавной, если разность двух соседних элементов не превосходит \(d\). Подсчитайте количество плавных последовательностей.

Программа получает на вход три числа: \(n\), \(k\), \(d\), \(1\le n\le 5000\), \(1\le k \le 5000\), \(0\le d \le 5000\).

Предполагается решение сложности \(O(nk)\). Также в этой задаче маленький лимит по памяти, предполагается, что решение использует \(O(k)\) памяти.

5 3 1

99

H: Двоичные последовательности содержащие \(k\) единиц, не содержащие \(m\) единиц подряд

По данным числам \(n\), \(k\), \(m\) определите количество двоичных последовательностей длины \(n\), содержащих \(k\) единиц и не содержащих \(m\) единиц подряд. Ограничения: \(1\le n\le 5000\), \(0\le k\le 5000\), \(1\le m\le 5000\).

Предполагается решение сложности \(O(n^2)\).

5 3 2

1