传送门：https://www.luogu.com.cn/problem/CF2205D
在一个排列中删去尽量少的数，使得不存在某个数比其两侧的数都大，每次删除的数必须满足比两侧都大。删除尽量少转换为保留尽量多。
如果没有删除的限制条件，有一个显然的 \(dp\)。用 \(dp_{a_i,0/1}\) 表示以 \(a_i\) 为结尾前 \(i\) 个数保留的最大数量，且第 \(a_i\) 比上一个选择的数小/大。转移方程就是 \(dp_{a_i,0}=\max\limits_{1\le j\le a_i} dp_{j,0}+1,dp_{a_i,1}=\max\limits_{a_i\le j\le n} \max (dp_{j,0},dp_{j,1})+1\)。过程用线段树维护即可。然后10分钟搓完发现漏看了个限制条件。。
加入删除的限制条件后，我们没办法在序列中直接从前往后dp了。我们手完模拟下这个过程。对于最大的数，我们显然必须删除其最左侧或最右侧的所有元素，然后考虑次大的数...。再结合合法序列的特征，因为不能出现先小后大再小的情况，所以序列只可能是先减后增的，我们可以枚举拐点，然后增减删除的方向就能被确定了。在单调减段，对于当前选择的数，我们找到左边第一个比他大的数，删除两者之间的数，这些数显然是比当前选择的数小的，只要当前选择的数不是单调减的末尾，在单调减段后面必定存在另外一个比他大的数，使得这次删除合法。或者不存在的话，