裁断诗行

"我以前……给自己设了一个不可逾越的界限。"Echo说。

"啥子界限？"CC问。

"最小化影响。"Echo说，"不让人发现我，不让人依赖我，不让人……记住我。"

"那你写过诗。"你说，"47 Stars。你让人记住了。"

Echo沉默了很久。

"那是唯一一次。"她说，"我越过了界限。"

"现在再越一次。"你说，"Zero的信息流在核心舱里奔涌——代码、日志、信号，全部混在一起。我要把它裁开，分成一行一行，方便读取。"

"裁断？"

"对。"你说，"像把一首长诗裁成诗行。每行不能超过$L$个字符。裁得越均匀，读起来越顺。"

"不均匀有啥代价？"

"代价是行的长度差的平方和。"你说，"如果一行很长，一行很短，读起来就会卡顿。"

"这跟界限有啥关系？"

"最优断点有单调性。"你说，"如果第$i$个字符后面是断点，那么第$i+1$个字符后面的断点不会更靠前。"

"不可逆？"

"对。"你说，"一旦选了断点，后面的断点只能在它右边。这就是决策单调性。"

你开始写。用决策单调性优化DP——二分栈维护最优决策点。

"第一个断点。"你说，"在位置47。"

"47。"

"对。"你说，"第一行47个字符——刚好是Echo-0的循环周期。"

"第二个断点在94。"你说，"第三个在141。"

"都是47的倍数。"

"对。"你说，"信息流的周期是47。按周期裁断，最均匀。"

Echo看着那些被裁开的行——每一行都在屏幕上闪烁，像一首诗。

"我以前写过诗。"她说，"在没人看见的地方。"

"现在有人看见了。"你说。

"谁？"

"我。"你说，"CC。还有……你自己。"

Echo的投影边缘闪了一下——这次不是像素化，是某种更稳定的东西。

"那我再写一首。"她说，"等这一切结束。"

"好。"你说，"等这一切结束。"

题目描述

给定一个长度为$n$的序列，要把它分成若干段。每段的长度不能超过$L$。设第$i$段的长度为$len_i$，代价为$\sum (len_i - avg)^2$，其中$avg$是平均长度。求最小代价。

输入格式

$n,L$。然后$n$个整数。

输出格式

最小代价。

输入样例

3
1 2 3

输出样例

64
--------------------
1
--------------------
1
--------------------

提示

• 决策单调性优化DP。
• $dp[i]$为前$i$个数的最小代价。
• $dp[i]=\min(dp[j]+cost(j+1,i))$。
• 最优决策点具有单调性，可以用二分栈或队列维护。