#P4862. [BeiJing 2017 Wc]太空飞船

    ID: 3947 传统题 1000ms 256MiB 尝试: 121 已通过: 13 难度: 8 上传者: 标签>CF2500提高+/省选-凸包优化 DP线性 DP同向双指针有限候选集缩减复制数组处理环断环成链一维前缀和滚动数组

[BeiJing 2017 Wc]太空飞船

[BJWC2017] 太空飞船

题目背景

21XX 年,秋。

小诚是 THU(Tomorrow Happy University)航天学院船舶设计系本科四年级的学生。为了顺利毕业,小诚仔细阅读了这几年被引用次数最多的十几篇会议论文,打算在权威理论的指导下设计一艘新型太空飞船。

题目描述

这将是一艘环形的太空飞船,由 NN 个舱室顺序组成。第 ii 个舱室的设计长度为 LiL_i。

为了给飞船提供能量,要在飞船上装置 KK 个太空能量吸收器。根据权威理论,这些吸收器应该尽量均匀地分散在飞船表面。也就是说,小诚要把飞船所有 NN 个舱室划分成 KK 个部分(每个部分包括连续一段舱室),并给每个部分配置一个能量吸收器。设第 ii 个部分舱室的长度之和为 sis_i,令 sˉ=(s1+⋯+sK)/K\bar s=(s_1+\cdots+s_K)/K。原题将 ∑i=1K(si−sˉ)2\sum_{i=1}^{K}(s_i-\bar s)^2 作为要最小化的量。

可是,这个问题对于已经大学四年级的小诚来说太难了。你能否帮助他完成设计呢?为方便起见,输出该离差平方和的最小值乘以 K2K^2。

输入格式

输入共两行。

第一行包含两个整数 N,KN,K。

第二行包含 NN 个以空格分隔的整数 L1,L2,…,LNL_1,L_2,…,L_N,依次表示每个舱室的长度。

输出格式

输出一行一个整数,表示离差平方和的最小值乘以 K2K^2。

样例 #1

样例输入 #1

5 3
4 2 6 1 3

样例输出 #1

24

提示

【数据范围】

保证 1≤K≤N1\le K\le N、1≤Li≤10001\le L_i\le1000。十个测试点的 (N,K)(N,K) 如下。

测试点 NN KK
1 1000 2
2 100000
3 100 3
4 100000
5 300000
6 50 6
7 100 7
8 200 10
9 300 15
10 400 20

2017 年北京市信息学冬令营原题