题解 P6398 【[COI2008] KOLEKCIJA】

pigstd · 2020-09-21 13:31:08 · 题解

upt on 2020.10.27：又修改了一些事实性错误，请管理员重新审核通过qwq。

upt on 2020.10.25：修改了一些事实性错误，请管理员重新审核通过qwq。

先从大到小排序，设 dp_i 表示包括 a_i 的情况下最小的答案

很容易推出方程 dp_i=\min(dp_j+\max(k,a_i-a_j+1))\ \ \ (j \le i-1)

但是直接搞的话是n^2的，跑不过去

我们可以把这个方程分成两部分：

1.dp_i=\min(dp_j+a_i-a_{j+1}+1)（当且仅当j \le i-1且a_i-a_j+1\le k）

这样的话，我们可以发现实际上是：dp_i=\min(dp_j-a_{j+1})+a_i+1，那么直接把每个 dp_j-a_{j+1} 预处理出来就行了

那么显然可以看成是dp_i=\min(dp_j)+k，那么显然当j最小的时候就可以了

怎么找到满足条件的j呢？二分就可以了

推完dp方程后怎么构造最后的答案呢？

如果 a_i-a_{i-1} \le dp_i-dp_{i-1} 那么显然第 i 个区间是和前一个数相邻的，所以可以说是右端点为 a_i，左端点为a_i-k+1

否则，显然是不相邻的，那么左端点是 a_i，右端点是a_i+k-1

还要考虑边界的情况。设 Min 表示 a_i 中最小的数。

• 如果左端点 \le Min-1 ，那么让这个点变为 Min，同时右端点也要相加。

• 如果右端点 \ge n+1，那么让这个点变为 n，同时左端点也要减。

最后还要记得记得排回来

code