题目名称	2225. [SDOI 2016 Round1] 征途
输入输出	`menci_journey1.in/out`
难度等级	★★★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	LGLJ 于2019-09-29加入
开放分组	全部用户
提交状态
分类标签	动态规划决策单调性优化斜率优化
	分享题解

通过：80，提交：300，通过率：26.67%
op_组撒头屯	100	0.000 s	0.00 MiB	C++
瑆の時間~無盡輪迴·林蔭	100	0.020 s	13.73 MiB	C++
LGLJ	100	0.116 s	4.13 MiB	C++
┭┮﹏┭┮	100	0.117 s	2.35 MiB	C++
Zayin	100	0.168 s	47.08 MiB	C++
HZOI_蒟蒻一只	100	0.178 s	0.14 MiB	C++
wumingshi	100	0.180 s	0.33 MiB	C++
甘罗	100	0.187 s	0.34 MiB	C++
Marvolo	100	0.194 s	0.34 MiB	C++
revenge	100	0.213 s	0.57 MiB	C++

关于征途的近10条评论(全部评论)
数据已修复，为了防止数据没有覆盖，已将文件名更改，请注意新的文件名。 LGLJ 2019-09-29 21:40 22楼
斜率优化啊…… 一上午加一下午啊…… 一下午加一晚上啊…… 一晚上又一早上啊…… 一早上又一下午啊…… 方差是啥都忘了…… 换元不会了…… 啥都不会了…… 身败名裂…… HZOI_蒟蒻一只 2017-05-14 16:19 21楼
为什么最后两个点开快读会TLE？是不是还少数据？求出题人解答 Marvolo 2017-03-21 13:22 20楼
似乎我写的斜率表达式有点长……所以就TLE…… FoolMike 2017-03-18 17:53 19楼
拜托能把后面两个点的错误数据改改吗？快被坑死了！ karles 2017-03-03 15:53 18楼
斜率优化吗？我没有用…… TenderRun 2016-06-12 12:01 17楼
%%% 我是蒟蒻膜拜楼上神犇。。。。。。神利·代目 2016-04-15 21:20 16楼
分治大法好 zys 2016-04-15 11:48 15楼
@menci 数据似乎有误,后两组数据路程好像不到n条吧... bhiaibogf 2016-04-14 20:48 14楼
回复 @Satoshi : 嘿嘿。友校题库，当然要捧场。 stone 2016-04-12 19:46 13楼

2225. [SDOI 2016 Round1] 征途

★★★☆ 输入文件：menci_journey1.in 输出文件：menci_journey1.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

Pine 开始了从 \( S \) 地到 \( T \) 地的征途。

从 \( S \) 地到 \( T \) 地的路可以划分成 \( n \) 段，相邻两段路的分界点设有休息站。
Pine 计划用 \( m \) 天到达 \( T \) 地。除第 \( m \) 天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。

设方差是 \( v \)，可以证明，\( v \times m ^ 2 \) 是一个整数。为了避免精度误差，输出结果时输出 \( v \times m ^ 2 \)。

【输入格式】

第一行两个数 \( n \)、\( m \)。

第二行 \( n \) 个数，表示 \( n \) 段路的长度。

【输出格式】

一个数，最小方差乘以 \( m ^ 2 \) 后的值。

【样例输入】

5 2

1 2 5 8 6

【样例输出】

【提示】

对于 \( 30\% \) 的数据，\( 1 \leq n \leq 10 \)。
对于 \( 60\% \) 的数据，\( 1 \leq n \leq 100 \)。
对于 \( 100\% \) 的数据，\( 1 \leq n \leq 3000 \)。
保证从 \( S \) 到 \( T \) 的总路程不超过 \( 30000 \)。

【来源】

SDOI2016 Round1 Day2

数据已由出题人修正