この記事で使うアルゴリズム
動的計画法
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp
この問題は動的計画法を用いて解くことができます。
方針
i
番目のブロックからj
番目のブロックまでのうちで取り除くことができるブロック数の最大値をdp[i][j]
として表します。
j-i
をd
として、奇数の場合は計算が簡単で、計算量を削減できます。
d
が偶数の場合dp[i+1][j-1]==d-1
の場合(間の区間が全て取り除ける場合)- 両端を取り除けるかを判定
dp[i+1][j-1]!=d-1
の場合(間の区間に取り除けないブロックがある場合)dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])
をk
でループ
d
が奇数の場合- 全ブロックを削除することはできないので、最善となる偶数の2パターンを考える
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
- 全ブロックを削除することはできないので、最善となる偶数の2パターンを考える
コード
1 | def solve(): |
記事情報
- 投稿日:2020年6月17日
- 最終更新日:2020年6月17日