https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=ACMP_497 2026-05-13T11:59:55Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=ACMP_497&diff=1166&oldid=prev 2014-12-24T17:23:42Z

<p>Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&amp;id_task=497 ACMP #497 — Индикатор] == Комментарии == Вид подз…»</p> <p><b>Новая страница</b></p><div>== Ссылка на задачу ==<br /> * [http://acmp.ru/?main=task&amp;id_task=497 ACMP #497 &amp;mdash; Индикатор]<br /> <br /> == Комментарии ==<br /> Вид подзадачи: d[n][k] &amp;mdash; первая цифра максимального n-значного числа из k полосок или -1, если такого числа не существует; d0[n][k] &amp;mdash; первая цифра максимального n-значного числа (возможно, с ведущими нулями) из k полосок или -1, если такого числа не существует. <br /> <br /> Рекуррентная формула: d0[n][k] = max(i : d0[n - 1][n - p[i]] &amp;ne; -1), где i &amp;isin; 0..9; d[n][k] = max(i : d0[n - 1][n - p[i]] &amp;ne; -1), где i &amp;isin; 1..9. В обоих случаях p[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}.<br /> <br /> База рекурсии: d[1][] = d0[1][] = {-1, -1, 1, 7, 4, 5, 9, 8, -1, -1, ...}.<br /> <br /> Вид ответа: Последовательность цифр (d[n][k], d0[n - 1][k - p[d[n][k]]], ...) Сложность O(N&lt;sup&gt;2&lt;/sup&gt;).<br /> <br /> Вычисление минимального числа производится аналогичной динамикой.<br /> <br /> [[Category: Сборник задач: ACMP]]<br /> [[Category: Задачи: Динамическое программирование &amp;mdash; два параметра]]</div>

Ctrlalt