問題例
数列aから好きな整数を好きなだけ取り除き、単調増加な数列を作るとき、その数列の長さの最大値を求めなさい。
引用: https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_h
最初に考えたこと
dp[i].first ... i - 1番目までの中からできる最長の単調増加数列の長さ
dp[i].second ... その時の数列内の最大値
として、Nの1重ループでdpの値を更新していく
実際に書いたコード
反例
N = 20
a = {19 11 10 7 8 9 17 18 20 4 3 15 16 1 5 14 6 2 13 12}
先ほどのコードだと、最初の19を必ず選んでしまい、19, 20だけしか選べずに長さが2になってしまう(答えは6)。
正しい解法
最長増加部分列を下記のような方法で動的に作っていく。
dp[i] ... 長さがi + 1であるよな増加部分列における最終要素の最小値(存在しない場合はINF)
dpの更新方法は、
- a[i]がdp[j](jはdp[j]がINFでない最大の数)よりも大きいとき、dp[j + 1] = a[i]
- a[i]がdp[j]よりも小さいとき、dp[k] = a[i] (kはdp[k] < a[i]となる最大の数)
であり、以下のコードのように書ける。