状态定义：
dp[i]：打印n个字符最小的磨损值
问题分析：
对于M来说:
如果没有M，只需要每打一个字启动一次即可。
如果M超级大，只需启动一次打完所有字即可。
由此可知，M决定了打印机启动的次数。对于Ci来说
显然：是C数组的前缀和。
dp[i]的状态转移公式(从第
j+1个字符到第i个字符)为：其中
j是我们要枚举的点，但是这样一来，时间复杂度就是的
-
斜率优化：
假设i点是由j或k点跳转而来（不妨设k<j）。那么j点优于k的条件是：化简后得到：
再令
，则上式可以转化为：
由此可见，如果点j和点k的斜率如果小于2sum[i]，那么就可以说点j优于点k。
为了更好地观察最终可能的结果集和，我们再来看一种凸情形：
我们能轻易地给出以下三种可能的关系：j优于k；k优于p，最优点为j
j优于k；p优于k，最优点为p或者j
k优于j；p优于k，最优点为p
我们可以发现，最优点要么是j，要么是p，反正不可能是凸出来的k点。由此我们可知最终的点集必须是一幅斜率递增的图像。当新插入的点发现斜率比前一对点的斜率更小，如图：则x5可以被剔除
x1开始寻找第一个斜率大于2sum[i]的一对点，不妨设为x3和x4，从上述式子的意义我们可以知道x4并没有比x3更优，所以从x3点出发到i的磨损是最低的。同时，维护这样的一个结构其实有一个名字叫做：单调队列
完整代码：
#include<iostream>
using namespace std;
#define MAX_N 1000000
#define SQ(a) ((a) * (a))
long long c[MAX_N + 5], sum[MAX_N + 5];
long long f[MAX_N + 5], dp[MAX_N + 5];
int q[MAX_N + 5], head, tail = 0;
int n, M;
void set(int i, int j) {
dp[i] = dp[j] + SQ(sum[i] - sum[j]) + M;
f[i] = dp[i] + SQ(sum[i]);
return ;
}
double slope(int i, int j) {
return 1.0 * (f[i] - f[j]) / (sum[i] - sum[j]);
}
int main() {
cin >> n >> M;
for (int i = 1; i <= n; i++) cin >> c[i], sum[i] = sum[i - 1] + c[i];
q[tail++] = 0;
for (int i = 1; i <= n; i++) {
while (tail - head >= 2 && slope(q[head], q[head + 1]) <= 2 * sum[i]) ++head;
set(i, q[head]); // 从单调队列的头部节点进行转移
while (tail - head >= 2 && slope(q[tail - 1], q[tail - 2]) > slope(q[tail - 1], i)) --tail;
q[tail++] = i;
}
cout << dp[n] << endl;
return 0;
}
