ACMP 497

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Ссылка на задачу

Комментарии

Вид подзадачи: d[n][k] — первая цифра максимального n-значного числа из k полосок или -1, если такого числа не существует; d0[n][k] — первая цифра максимального n-значного числа (возможно, с ведущими нулями) из k полосок или -1, если такого числа не существует.

Рекуррентная формула: d0[n][k] = max(i : d0[n - 1][n - p[i]] ≠ -1), где i ∈ 0..9; d[n][k] = max(i : d0[n - 1][n - p[i]] ≠ -1), где i ∈ 1..9. В обоих случаях p[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}.

База рекурсии: d[1][] = d0[1][] = {-1, -1, 1, 7, 4, 5, 9, 8, -1, -1, ...}.

Вид ответа: Последовательность цифр (d[n][k], d0[n - 1][k - p[d[n][k]]], ...) Сложность O(N2).

Вычисление минимального числа производится аналогичной динамикой.