太空飞船 - ROJ

【题目描述】

小诚准备设计一艘环形的太空飞船，由 $N$ 个舱室顺序组成。第 $i$ 个舱室的设计长度为 $L_i$ 。为了给飞船提供能量，要在飞船上装置 $K$ 个太空能量吸收器。这些吸收器应该尽量均匀地分散在飞船表面。也就是说，小诚要把飞船所有 $N$ 个舱室划分成 $K$ 个部分（每个部分包括连续一段舱室），并给每个部分配置一个能量吸收器。设第 $i$ 个部分舱室的长度之和为 $s_i$ ，则要令方差 $\sum_{i=1}^{k}(s_i-s_{avg})^2$ 尽量小。其中 $s_{avg}$ 是 $K$ 个部分的平均长度。可是，这个问题对于小诚来说太难了。你能否帮助他完成设计呢？为方便起见，输出方差最小值与K的平方的乘积。

【输入】

第一行，两个整数 $N，K$ 。第二行， $N$ 个整数 $L_1, L_2, …, L_N$ ，由空格隔开。依次表示每个舱室的长度。

【输出】

输出一行，为一个整数，表示方差最小值与 $K^2$ 的乘积。

【输入样例】

5 2
4 2 6 1 3

【输出样例】

【提示】

【输入样例2】

5 3
4 2 6 1 3

【输出样例2】

【样例解释】第一组样例。要将飞船分为 $2$ 段，最优划分方法为 $[2 6] [1 3 4]$ 。第二组样例。要将飞船分为 $3$ 段，最优划分方法为 $[4 2] [6] [1 3]$ 。【数据规模】本题一共有10 个测试点。下表是每个测试点的数据规模：

#1	N=1000	K=2	#6	N=50	K=6
#2	N=100000	#7	N=100	K=7
#3	N=100	K=3	#8	N=200	K=10
#4	N=100000	#9	N=300	K=15
#5	N=300000	#10	N=400	K=20

对于100%的数据， $1≤L_i≤1000$ 。

5 3\n4 2 6 1 3