问题2390--胶带(tape)

2390: 胶带(tape)

时间限制: 1 Sec  内存限制: 128 MB
提交: 24  解决: 16
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY有一根长的木棒,这个木棒划了m个刻度,编号为1~m,每个刻度长度为一厘米。现在这根木棒在某些刻度处出现了裂痕,总共有n处裂痕,需要你帮忙修补它。
你现在有一卷无限长的胶带,可以利用它去修补裂痕,修补方式为:撕下长度为t的胶带,从s段开始贴,可以把[s, s+t-1]这段区间内的裂痕都修补。BSNY规定,最多可以撕k次胶带,问你,最小可以用多少总长度修补所有的裂痕?
例如n=4, m=100, k=2,表示100个刻度中有4个裂痕,最多撕两次胶带来修补。4个裂痕位置为:20, 30, 75, 80。你可以使用长度为11的胶带去修补20和30,再使用长度为6的胶带去修补75和80,总共长度为17,为最小总长度。

输入

第一行输入n, m, k
第二行输入n个整数bi,表示裂痕位置,保证1<=b1<b2<…<bn<=m

输出

输出最小总长度

样例输入 Copy

5 100 3
1 2 4 60 87

样例输出 Copy

6

提示

50%数据 1<=n<=1000,  m<=1000
100%数据 1<=n<=10^5,   n<=m<=10^9,   1<=k<=n

来源/分类