题目的意思是有个打印机很老了，现在要打印单词，每个单词打印都有耗费价值，每次打印几个单词都符合题目给出的式子：

问，最少的耗费价值。第一次接触概率dp，介绍几篇题解吧，结合起来看更好理解。

http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html(针对这个题讲的很容易懂，但是中间有些错误，还请不要纠结，下面评论区有指正。)

http://www.cnblogs.com/kuangbin/archive/2012/08/26/2657650.html(结合上一片博客食用更佳，看完上面的如果纠结错误，看这篇可以解惑)

http://blog.csdn.net/lxc779760807/article/details/51366552（斜率dp优化小结，写的不错）

代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=500005;
int n, m;
int dp[maxn], sum[maxn], que[maxn];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int getDp(int i, int j){
    return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;
}
int getUp(int j, int k){
    return dp[j]+sum[j]*sum[j]-dp[k]-sum[k]*sum[k];
}
int getDown(int j, int k){
    return 2*(sum[j]-sum[k]);
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        sum[0]=dp[0]=0;
        for(int i=1;i<=n;i++){
            sum[i]=read();
            sum[i]+=sum[i-1];
        }
        int head=0, tail=0;
        que[tail++]=0;
        for(int i=1;i<=n;i++){
            while(head+1<tail && getUp(que[head+1], que[head])<=sum[i]*getDown(que[head+1], que[head]))
                head++;     //找到最优解
            dp[i]=getDp(i, que[head]);
            while(head+1<tail && getUp(i, que[tail-1])*getDown(que[tail-1], que[tail-2])<=getDown(i, que[tail-1])*getUp(que[tail-1], que[tail-2]))
                tail--;     //删除斜率变小的点
            que[tail++]=i;  //当前点放入队列
        }
        printf("%d\n", dp[n]);
    }
    return 0;
}