https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=ACMP_673 2026-05-13T11:41:23Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=ACMP_673&diff=1158&oldid=prev 2014-12-18T23:39:03Z

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

Ctrlalt