dp斜率优化小计

对于斜率dp优化，强烈推荐一篇博客http://www.cnblogs.com/Rlemon/p/3184899.html

感觉这篇博客把斜率dp讲的很全面了

hdu3507的题解：

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/4/21 星期二 23:44:54
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 typedef long long LL;
17 
18 const int MaxA=5e5+7;
19 
20 int N, M;
21 LL sum[MaxA];
22 int deque[MaxA];
23 LL f[MaxA];
24 LL func(int i, int j) {
25     return (sum[i]-sum[j])*(sum[i]-sum[j])+M+f[j];
26 }
27 LL getY(int i, int j) {
28     return (sum[j]*sum[j]+f[j])-(sum[i]*sum[i]+f[i]);
29 }
30 LL getX(int i, int j) {
31     return sum[j]-sum[i];
32 }
33 void solve() {
34     int front=0, tail=0;
35     f[0]=0;
36     deque[tail++]=0;
37     for(int i=1; i<=N; i++) {
38         while(front+1<tail && func(i, deque[front])>=func(i, deque[front+1])) front++;
39         f[i]=func(i, deque[front]);
40         while(tail-1>front &&
41                 getY(i, deque[tail-1])*getX(deque[tail-1], deque[tail-2])<=
42                 getY(deque[tail-1], deque[tail-2])*getX(i, deque[tail-1])) --tail;
43         deque[tail++]=i;
44     }
45     printf("%lld
", f[N]);
46 }
47 int main() {
48 #ifndef ONLINE_JUDGE
49     freopen("in", "r", stdin);
50     //freopen("out", "w", stdout);
51 #endif
52     while(~scanf("%d%d", &N, &M)) {
53         sum[0]=0;
54         for(int i=1; i<=N; i++) {
55             int x;
56             scanf("%d", &x);
57             sum[i]=sum[i-1]+x;
58         }
59         solve();
60     }
61     return 0;
62 }

hdu3507