https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=ACMP_560 2026-05-13T12:33:41Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=ACMP_560&diff=1305&oldid=prev 2015-01-13T23:56:19Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 23:56, 13 января 2015</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l15">Строка 15:</td> <td colspan="2" class="diff-lineno">Строка 15:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Сборник задач: ACMP]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Сборник задач: ACMP]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Задачи: Динамическое программирование &amp;mdash; два параметра]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Задачи: Динамическое программирование &amp;mdash; два параметра <ins style="font-weight: bold; text-decoration: none;">+ привязка</ins>]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Задачи: Дерево отрезков]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Задачи: Дерево отрезков]]</div></td></tr> </table>

Ctrlalt https://acm.khpnets.info/w39/index.php?title=ACMP_560&diff=1300&oldid=prev 2015-01-13T23:51:44Z

<p>Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&amp;id_task=560 ACMP #560 — Остановки] == Похожие задачи == * Инт…»</p> <p><b>Новая страница</b></p><div>== Ссылка на задачу ==<br /> * [http://acmp.ru/?main=task&amp;id_task=560 ACMP #560 &amp;mdash; Остановки]<br /> <br /> == Похожие задачи ==<br /> * [[Интернет-олимпиада 12.11.2005, усложнённый уровень, F]]<br /> <br /> == Комментарии ==<br /> Вид подзадачи: d[i][j] &amp;mdash; минимальная стоимость постройки i остановок, если последняя из них заканчивается в клетке a[j]. <br /> <br /> Рекуррентная формула: d[i][j] = min(d[i - 1][k] + &amp;sum;a[t]), где k &amp;isin; (j - l - R)..(j - l - r), t &amp;isin; (j - l + 1)..j.<br /> <br /> База рекурсии: Если j &lt; r + l - 1, или i &amp;times; (l + r) &gt; j + 1, или i &amp;times; (l + R) &lt; j + 1, то d[i][j] = INF. Если s[1][j] &amp;ne; INF, то d[1][j] = &amp;sum;a[t]; где t &amp;isin; (j - l + 1)..j.<br /> <br /> Вид ответа: min(d[n][k]), где k &amp;isin; (L - R - 1)..(L - r - 1). Сложность O(N &amp;times; L &amp;times; R), с деревом отрезков &amp;mdash; O(N &amp;times; LlogL).<br /> <br /> [[Category: Сборник задач: ACMP]]<br /> [[Category: Задачи: Динамическое программирование &amp;mdash; два параметра]]<br /> [[Category: Задачи: Дерево отрезков]]</div>

Ctrlalt