Стрічка#128

Стрічка (Editorial)

Це класична задача динамічного програмування, по суті — варіант задачі про розмін монет, тільки максимізуємо кількість частин.

Нехай — максимальна кількість частин, на яку можна розрізати стрічку довжини рівно . Значення позначає, що така довжина недосяжна.

База: \mathrm{dp}[0] = 0 — порожню стрічку розрізано на нуль частин.

Перехід: останній відрізаний шматок має довжину , або , тому

\mathrm{dp}[i] = 1 + \max\bigl(\mathrm{dp}[i-a],\; \mathrm{dp}[i-b],\; \mathrm{dp}[i-c]\bigr),

де беруться лише ті варіанти, для яких i \ge x і стан \mathrm{dp}[i-x] досяжний.

Відповідь — . Умова гарантує, що коректне розрізання існує, тому це значення не буде .

Складність — за часом і пам'яттю, що при N \le 4000 миттєво.

Зверніть увагу, що жадібний підхід (щоразу відрізати найкоротший шматок) тут не працює: він може привести до довжини, яку вже неможливо дорізати. Саме тому потрібна динаміка. Значення , , можуть збігатися — на алгоритм це ніяк не впливає.