[AtCoder] ACL Beginner Contest D – Flat Subsequence

問題

方針

最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。

まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( i \) で終わる最長部分列の長さとします。\( d \) は \( 0 \) で初期化し、\( i – 1 \) まで \( d \) が構築できたとして、\( A_i \) について考えます。\( d(A_i) \) の更新は、

\[d(A_i) \leftarrow \max \left( d(A_i – K), d(A_i – K + 1), \cdots d(A_i + K)\right) + 1\]

となります。\( A_i – K \leq A_i \leq A_i + K \) となるので常に更新して大丈夫です。

コード

参考