競プロ初中級者100問

DPL1D 最長増加部分列

この記事で使うアルゴリズム

動的計画法
二分探索

はじめに

カテゴリー競プロ初中級者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
2
3
4
5
6
7
8
9
import bisect
INF = 10**10
N = int(input())
dp = [INF] * (N)
for n in range(N):
    a = int(input())
    i = bisect.bisect_left(dp, a)
    dp[i] = a # aがA[:n]中で最大なら、最も左のINFが更新される
print(bisect.bisect_left(dp, INF)) # 最後にINF以外の要素数を数える

記事情報

  • 投稿日：2020年5月21日
  • 最終更新日：2020年5月21日