箱根駅伝 DP
Kyopro Encyclopedia of Algorithms

これはステージング環境です。5 秒後に自動的に本番環境 (https://noshi91.github.io/algorithm-encyclopedia) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /algorithm-encyclopedia/tenkei/hakoneekiden-dp#noredirect を利用してください。

name: 箱根駅伝 DP
short description: 区間の集合を構成するような DP であって「左端は決まったが右端はまだ決まってない区間の数」と「右端は決まったが左端はまだ決まってない区間の数」を状態とする DP のこと。

箱根駅伝 DP とは、区間の集合を構成するような DP であって「左端は決まったが右端はまだ決まってない区間の数」と「右端は決まったが左端はまだ決まってない区間の数」を状態とする DP のこと。状態が何であるかに基づく DP の分類のひとつ。

例題

AOJ 2439: 箱根駅伝^archive.org
- この問題が呼称の由来である。
AtCoder Beginner Contest 134: F - Permutation Oddness^archive.org

changelog

2020年01月16日「記事作成」 authors: kimiyuki, reviewers:none

license

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.