#P2380. E51*【斜率优化】打印文章[HDU3507]

E51*【斜率优化】打印文章[HDU3507]

【题意】

给出 NN 个非负整数 CiC_i,将它们分成连续的若干段,每段的费用为此段和的平方,还要加一个常数 LL,即 (Ci)2+L(\sum C_i)^2+L

现在想求出一种最优方案,使得总费用之和最小。

【输入格式】

包含多组测试数据,对于每组测试数据:

第一行包含两个整数 NNLL

第二行为 NN 个整数。

【输出格式】

输出仅一个整数,表示总费用的最小值。

5 5
5 9 5 7 5
230

【数据范围与提示】

对于全部数据,0N5×105,0Ci,L10000\le N\le 5\times 10^5, 0 \le C_i,L \le 1000