这是一道典型的思路难题，代码20行以内，所以就不贴代码了。
15pts n ≤ 20 , m ≤ 10 n\leq 20,m\leq 10 n≤20,m≤10
这个好拿，但我没去拿，暴力枚举即可
验证部分，可以发现，由于这些长度为
k
k
k的区间可以重叠，重叠的部分对答案没有影响，所以，对于任何一个长度大于
k
k
k的连续段都是可以拼出的
70pts n ≤ 1 0 9 , m ≤ 5000 n\leq 10^9,m\leq 5000 n≤109,m≤5000
其实中间还有30pts与50pts，但不如70pts好拿。
观察可以发现，
n
n
n已然几乎没用，所以只考虑
m
m
m，可以发现数据允许
O
(
m
2
)
O(m^2)
O(m2)通过
考虑
d
p
dp
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
k
k，且覆盖点最多，就是距离
i
i
i最远
j
j
j的满足
a
[
i
]
−
a
[
j
]
+
1
<
k
a[i]-a[j]+1<k
a[i]−a[j]+1<k且
i
≥
j
i\geq j
i≥j
于是就可以暴力枚举
100pts
这就简单了，因为 a i a_i ai递增，并且不存在距离最大值，尺取即可。