CF1919 C. Grouping Increases

给定一个长为 \(n\) 的序列 \(a\)，你需要将该序列恰好分成两个子序列 \(s,t\)。定义一个长为 \(m\) 的序列 \(b\) 的代价为 \(\displaystyle p(b)=\sum_{i=1}^{m-1}[b_i<b_{i+1}]\)，求 \(p(s)+p(t)\) 的最小值。每个测试点 \(t\) 组测试用例。

思路贪心。

可以发现答案的贡献只与每相邻两个数有关，因此维护 \(x, y\) 表示当前两个子序列的结尾数字。为了更一般性，令 \(x \ge y\)。

此时，对于一个新元素 \(a_i\)，我们要考虑将其放入哪个子序列后，而且我们希望修改后 \(x, y\) 的值尽量变大，因为这会对后续造成更有利的影响。

此时共有三种情况：

• \(a_i > x\)：这意味着无论放在哪个子序列都会导致答案多一，但是显然将 \(y \gets a_i\) 更优。因为这会使 \(x, y\) 增大的尽量多。
• \(a_i > y\)：如果 \(y \gets a_i\)，那么答案会多一，显然不优。因此 \(x \gets a_i\)。
• \(a_i \le y\)：显然此时放在哪个子序列中答案都不会加一。但是这样修改后一定会让它们变小，所以我们选择 \(y \gets a_i\)，即让损失较小。

根据上述规则模拟即可。代码。