#PQJ1507x8204. QOJ 1507_8204
QOJ 1507_8204
2017 年北京市信息学冬令营结业测试 2
太空飞船 【题目描述】 21XX 年,秋。 小诚是THU(Tomorrow Happy University)航天学院船舶设计系本科四年级的学 生。为了顺利毕业,小诚仔细阅读了这几年被引用次数最多的十几篇会议论文,打算在权威 理论的指导下设计一艘新型太空飞船。 这将是一艘环形的太空飞船,由N 个舱室顺序组成。第i 个舱室的设计长度为Li。为 了给飞船提供能量,要在飞船上装置K 个太空能量吸收器。 根据权威理论,这些吸收器应该尽量均匀地分散在飞船表面。也就是说,小诚要把飞船 所有N 个舱室划分成K 个部分(每个部分包括连续一段舱室),并给每个部分配置一个能量 吸收器。设第i 个部分舱室的长度之和为si,则要令方差 ∑ (𝑠𝑖−𝑠_𝑎𝑣𝑔)2 𝑖=1..𝐾
尽量小。其中 s_avg 是K 个部分的平均长度。 可是,这个问题对于已经大学四年级的小诚来说太难了。你能否帮助他完成设计呢? 为方便起见,输出方差最小值与K 的平方的乘积。
【输入格式】
输入文件名为spaceship.in。 第一行,两个整数N,K。 第二行, N 个整数L1, L2, …, LN,由空格隔开。依次表示每个舱室的长度。
【输出格式】
输出文件名为spaceship.out。
输出一行,为一个整数,表示方差最小值与K2 的乘积。
【样例输入1】
5 2 4 2 6 1 3
【样例输出1】
0
【样例输入2】
5 3 4 2 6 1 3
【样例输出2】
24
【样例解释】
第一组样例。要将飞船分为2 段,最优划分方法为 [2 6] [1 3 4]。
第二组样例。要将飞船分为3 段,最优划分方法为 [4 2] [6] [1 3]。
2017 年北京市信息学冬令营结业测试 3
【数据规模与约定】 本题一共有10 个测试点。 下表是每个测试点的数据规模:
#1 N = 1,000 K = 2 #6 N = 50 K = 6 #2 N = 100,000 #7 N = 100 K = 7 #3 N = 100 K = 3 #8 N = 200 K = 10 #4 N = 100,000 #9 N = 300 K = 15 #5 N = 300,000 #10 N = 400 K = 20
对于100%的数据,1 ≤ Li ≤ 1,000。