P2215 [HAOI2007] 上升序列-526互联

考虑一个长度为 \(L\) 的最长上升子序列 \(P\)，以它的第 \(i\) 个元素 \(a_{x_i}\) 开头的最长上升子序列长度至少为 \(L-i+1\)。反之，若一个数满足以其开头的最长上升子序列长度至少为 \(L-i+1\) 则这个数必定可以作为 \(P\) 的第 \(i\) 个元素。

所以我们可以先倒着跑一遍最长下降子序列，求出以每个数为开头的最长上升子序列。接着贪心地考虑，从前往后扫能取就取，显然最优。