题解 P2501 【[HAOI2006]数字序列】

灵乌路空 · 2020-07-09 09:55:50 · 题解

知识点: DP

原题面

太妙了，学到虚脱。

题意简述

给定一长度为 n 的数列 a，可将 a_i 改为任意整数 k，代价为 \mid a_i -k\mid。
求使数列变为单调严格上升序列，最少需要改变的个数。
及改变数最少时，最小的代价和。

分析题意

先搞掉第一问。

需要改变最少，则需保留得尽可能多。
考虑保留两个数的条件，对于 a_i,a_j(i < j)，若可保留，说明 a_i < a_j 且改变 [i+1,j-1] 内的数，可使序列 [i,j] 严格上升。

如数列 1, 4, 5, 3 (无歧义)，虽然满足 1<3，但它们中间的两个数无论改成多少，都无法满足单增性质。

显然保留 a_i,a_j 的条件为：a_j-a_i \ge j-i。
移项，得 a_j - j \ge a_i - i。
发现保留 a_i 的条件为 a_i-i 单调不降。

设 b_i = a_i - i。 使用经典 O(n\log n) 的方法，求数列 b 的最长不下降子序列长度，即为答案。

来搞第二问。

发现使 a_i 单调上升的代价，等价于使 b_i 单调不降的代价。
有个结论：
对于区间 [l,r]，使其单调不降，则存在分界点 k，使 b_i = b_l(i\le k), b_j = b_r (j>k)，此时代价最小。

如何证明这个听起来很扯皮的结论？

考虑做第一问时，顺便维护一下每个数的从哪里转移而来。
设转移前驱为 pre_i。
显然，pre_i 为满足 b_i \ge b_{pre_i} 的，且使子序列最长的位置。
则不存在 pre_i<j<i，使 b_j\le b_i，否则 pre_i = j 显然更优。

考虑 pre_i 和 b_i 之间的数 b_j，一定满足 b_j < b_{pre_i} 或 b_j>b_i，它们一定要被修改。
设 b_j 修改后为 c_j，显然 c_j 单调不降，且 b_{pre_i} \le c_j\le b_i。
则有下图形式：

上图给出了一种修改的方案，考虑能否调整方案，使答案更优。
分类讨论： 对于一段被改为 c 的连续区间 [l,r]：

1. 若 b_j < b_{pre_i} 的数量大于 b_j > b_{pre_i} 的数量，则 c 越小，代价越小。
   又要保证单调不降，则 c = c_{l-1} 时最优。
2. 若 数量相反，分析过程同上，c = c_{r+1} 时最优。
3. 若 数量相等，c 可取任意值。

则可对此方案进行调整：



发现满足结论形式。

则对于任意不满足结论的方案，均可进行调整，使代价更小，最终必定调整至结论中的形式。

令 g_i 表示，最后一位是 b_i 时单调不降的代价。
枚举满足条件的前驱 pre，转移 b_i， 枚举的前缀满足：

• 以b_{pre}结尾的 最长不降子序列长度 = 以 b_i 结尾的 - 1。

之后枚举分界 k，求得最小的代价。 有：

后面那一大堆 \sum 可以用前缀后缀和优化。
复杂度 O(n^2) 级别？但数据随机，[pre_i,i] 的长度较小，可以跑过去。

代码实现

代码中用 vector 记录长度为 i 的最长不降子序列的结尾，再通过判断确定转移前缀。