P2501 [HAOI2006] 数字序列

先来看第一问。

发现直接做要考虑两数中间的数能否变得合法，所以按套路将 \(a_i\) 减去 \(i\)，这样就只要变成单调不降，只要两数合法中间的数就一定能变得合法。考虑不改变的那些数，它们一定单调不降，所以答案就是序列总长度减去最长不下降子序列的长度。

接下来看第二问，尝试观察一些性质：

• 可能有多个最长不下降子序列，每个子序列的答案都有可能成为最小值。
• 子序列中相邻的两项之间的任意一个数要么不小于前一项，要么不大于后一项，否则将其并入子序列长度会更长。

现在我们有两个相邻的数，都需要修改，前者大于后者。显然，将它们修改成两数之间的任意一个数代价都是最小的。应用到子序列的相邻两项 \(i\) 和 \(j\) 之间，假设某种情况第 \(k\) 个数修改成了 \(b_k\)，将相同数合并，那么我们就得到了一个新的序列 \(b\)。考虑其中相邻的三项 \(x,y,z(i\leq x<x+1=y<y+1=z\leq j,b_x<b_y<b_z)\)，我们将 \(b_y\) 修改成 \(b_x\) 或 \(b_z\)，要么代价都不变，要么有一种代价会减小。按这样一直搞下去最终只会剩下 \(i\) 和 \(j\) 这两项，所以我们就得到了一个结论：最优解一定存在一个断点 \(k\)，使得 \(b_i=b_k<b_{k+1}=b_j\)。

然后用这个结论直接暴力就行了，时间复杂度 \(O(n\log a+n^3)\)，但因为数据是随机的所以根本跑不满。