https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=ACMP_683 2026-06-02T22:10:28Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=ACMP_683&diff=1292&oldid=prev 2015-01-12T15:51:05Z

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

Ctrlalt