十一月

P10991 选段排序

给定长度为 \(n\) 的序列 \(a\)，和 \(p,q(p<q)\)，可以进行一次区间排序，最大化 \(a_q-a_p\)。

不会做，贺题解。

结论：排序的区间 \([l,r]\) 要么 \(l=p\) 要么 \(r=q\)。

证明：对于 \(l=p\) 的情况，如果此时 \(r<q\) 则 \(a_q\) 不变，而 \(l\) 左移不会使 \(a_p\) 变小。

如果\(r\ge q\)，\(l\) 左移如果加入一个小于当前 \(a_p\) 的数则结果不变，加入的数大小在 \(a_p\) 和 \(a_q\) 之间则 \(a_q\) 不变 \(a_q\) 变小。只有加入的数 \(>a_q\) 才有可能对答案有贡献。

在上述状态下，如果把 \(r\) 左移，删去的数 \(\ge a_p\)，则 \(a_q\) 变大，\(\le a_p\) 和上述一样贡献。

P11013 C 粉碎

题挺好就是不会做。

长度为 \(n\) 的序列 \(a\)。依次加入一个双向队列中，可以左入也可以右入，当队列中出现两个相同的数时，把这两个数以及两个数之间的数删去，求最多删几个数。

容易证明的是删除的区间是一段前缀，我们只要找到最后一组被删掉的数就可以了。

考虑 \(dp\)