题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3507
题目大意：概题意就是要输出N个数字a[N]，输出的时候可以连续连续的输出，每连续输出一串，它的费用是 “这串数字和的平方加上一个常数M”。（N<=500000，M<=1000）
解题思路：参考了这里的思路，这算是我写得第一题斜率优化DP了，当做模板来用吧。推理下次补上。
我们设dp[i]表示输出到i的时候最少的花费，sum[i]表示从a[1]到a[i]的数字和。于是状态转移方程就是：
dp[i]=min(dp[i]，dp[j]+M+(sum[i]-sum[j])^2）（0<=j<i）
但是题目给出的N为最大500000，这个O（n^2）的算法显然会超时，于是可以用斜率优化，利用队列维护单调性进行优化，将复杂度降至O（n）。
代码：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 const int N=5e5+5;
7
8 int n,m,head,tail;
9 int dp[N],sum[N],q[N];//q为需要维护的队列
10
11 // dp[i]= min{ dp[j]+M+(sum[i]-sum[j])^2 }
12 int getDP(int i,int j){
13 return dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]);
14 }
15
16 //yj-yk
17 int getUP(int j,int k){
18 return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]);
19 }
20
21 //xj-xk
22 int getDOWN(int j,int k){
23 return 2*(sum[j]-sum[k]);
24 }
25
26 int main(){
27 while(~scanf("%d%d",&n,&m)){
28 dp[0]=sum[0]=0;
29 for(int i=1;i<=n;i++){
30 scanf("%d",&sum[i]);
31 sum[i]+=sum[i-1];
32 }
33 head=tail=0;
34 q[tail++]=0;
35 for(int i=1;i<=n;i++){
36 //队列元素有两个以上时,维护g(k,j)=(yj-yk/xj-xk)<sum[i]，注意分母为0不能直接比较斜率
37 while(head+1<tail&&!(getUP(q[head],q[head+1])<sum[i]*getDOWN(q[head],q[head+1]))){
38 head++;//相当于淘汰q[head]也就是k
39 }
40 dp[i]=getDP(i,q[head]);
41 //队列元素有两个以上时,维护g(k,j)<g(j,i)
42 while(head+1<tail&&!(getUP(q[tail-1],i)*getDOWN(q[tail-2],q[tail-1])>getUP(q[tail-2],q[tail-1])*getDOWN(q[tail-1],i))){
43 tail--;
44 }
45 q[tail++]=i;
46 }
47 printf("%d\n",dp[n]);
48 }
49 return 0;
50 }