猫猫cpu的缓存

原题过长，放一下题目大意

题目大意

给你 $m$ 个 $1$ 到 $n$ 之间的整数，你要找到若干个大小为固定的 $k$ 的闭区间，使得所有这些数都在你找到的某个区间内。你需要最小化这些区间的并集的大小，并输出此大小。本题里区间/区间并集的大小，被定义为，这个区间/区间并集里整数的个数

样例

样例输入1

10 3
5
4
5
8
7
6

样例输出1

5

样例解释：

取 { 4 , 5 , 6 , 7 , 8 } \{4,5,6,7,8\} {4,5,6,7,8}
共需要 5 个字节

样例输入2

15 4
6
6
14
11
3
8
5

样例输出2

10

数据范围

$100\%n\le 10^9,m\le 3\ast 10^5$

闲话

这题不知从哪里得来的，只知道至少有强蓝弱紫甚至中紫的难度。
在得到后，我立刻做出了正确的分析，却因为一种特殊的情况而未能想出正确的状态转移方程，最终没有做出
至于部分分，在原题数据范围中有，但我没有给出，我会在下面的题解部分给出详细介绍

题解

这是一道典型的思路难题，代码20行以内，所以就不贴代码了。

15pts $n\le 20,m\le 10$

这个好拿，但我没去拿，暴力枚举即可
验证部分，可以发现，由于这些长度为$k$的区间可以重叠，重叠的部分对答案没有影响，所以，对于任何一个长度大于$k$的连续段都是可以拼出的

70pts $n\le 10^9,m\le 5000$

其实中间还有30pts与50pts，但不如70pts好拿。
观察可以发现，$n$已然几乎没用，所以只考虑$m$，可以发现数据允许$O(m^2)$通过
考虑$dp$，发现存在以下两种情况

对于第一种情况，较好考虑，状态转移方程为
d p [ i ] = m i n i ≥ j { d p [ j − 1 ] + ( a [ j ] − a [ i ] ) + 1 } dp[i]=min_{i\geq j}\{dp[j-1]+(a[j]-a[i])+1\} dp[i]=mini≥j​{dp[j−1]+(a[j]−a[i])+1}
对于第二种情况，我们固然希望该区间段长度最短，为$k$，且覆盖点最多，就是距离$i$最远$j$的满足$a[i]-a[j]+1<k$且$i\ge j$

于是就可以暴力枚举

100pts

这就简单了，因为$a_i$递增，并且不存在距离最大值，尺取即可。