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).
Вычисление минимального числа производится аналогичной динамикой.