打印文章

提交数: 28, 通过率: 60.71%, 平均分: 66.07

题目描述:

给出N个单词，每个单词有个非负权值Ci，现在要将它们分成连续的若干段，每段的代价为此段单词的权值和的平方，还要加一个常数M，即 (sigma(Ci)2+M 。现在想求出一种最优方案，使得总费用之和最小。

输入格式:

包含多组测试数据，对于每组测试数据。

第一行包含两个整数N和M（0<=N<=500000，0<=M<=1000）。

第2-N+1行为N个整数。

输出格式:

输出仅一个整数，表示最小的价值。

样例输入:

5 5
5
9
5
7
5
3 0
1
2
3

样例输出:

230
14

提示:

对于50%的数据，N<=24000，数据组数<=10

对于100%的数据，每个测试点的N总和<=5000000

HDU原题提交地址

HDU原题Vjudge提交地址

时间限制: 3000ms
空间限制: 64MB

来源: 数据 by qq1010903229