この記事で使うアルゴリズム
動的計画法
二分探索
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D&lang=ja
この問題は動的計画法と二分探索で解くことができます。
方針
dp[n-1]
に長さnの増加部分列のうち、右端の値として考えられる最小値
を格納します。
数列A
の各要素をクエリとした二分探索を行い、dp
を更新していけば良いです。
最終的には構成可能なdp[n-1]
にはINF
以外の値が入るので、それらを数え上げれば答えとなります。
コード
1 | import bisect |
記事情報
- 投稿日:2020年5月21日
- 最終更新日:2020年5月21日