HDU3507-Print Article-斜率dp入门题

为了学CDQ分治，从斜率dp和凸包开始做吧。。

代码就是维护一个凸包。利用递增的性质丢掉不合适的点。

http://www.cnblogs.com/Rlemon/p/3184899.html

代码学的上面很模板

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 //typedef long long LL;
 6 
 7 struct Point{
 8     int x,y;
 9     Point (int _x=0,int _y=0):x(_x),y(_y){}
10     Point operator - (const Point &rhs) const
11     {
12         return Point(x-rhs.x,y-rhs.y);
13     }
14 };
15 typedef Point Vector;
16 inline int Cross(const Vector &u,const Vector &v)
17 {
18     return u.x*v.y - u.y*v.x;
19 }
20 
21 const int maxn = 5e5+10;
22 int N,M;
23 int sum[maxn],save[maxn];
24 int dp[maxn];
25 struct dequeue{
26     Point q[maxn];
27     int head,tail;
28     void init()
29     {
30         head = 1;tail = 0;
31         //q[head].x = 0;q[head].y = 0;
32     }
33     void push(const Point &u)
34     {
35         while(head < tail && Cross(q[tail]-q[tail-1],u-q[tail])<=0) tail--;
36         q[++tail] = u;
37     }
38     Point pop(const int &k)
39     {
40         while(head < tail && k*q[head].x+q[head].y >= k*q[head+1].x + q[head+1].y) head++;
41         //printf("head:%d x:%d y:%d
",head,q[head].x,q[head].y);
42         return q[head];
43     }
44 }H;
45 
46 int main()
47 {
48     //freopen("input.txt","r",stdin);
49     while(~scanf("%d%d",&N,&M))
50     {
51         sum[0] = 0;
52         for(int i=1;i<=N;i++)
53         {
54             scanf("%d",&save[i]);
55             sum[i] = sum[i-1]+save[i];
56         }
57         H.init();
58         H.push(Point(0,0));
59         dp[0] = 0;
60         for(int i=1;i<=N;i++)
61         {
62             int k = -2*sum[i];
63             Point u = H.pop(k);
64             //printf("i:%d k:%d u.x:%d u.y:%d
",i,k,u.x,u.y);
65             dp[i] = u.x*k + u.y + sum[i]*sum[i] + M;
66             H.push(Point(sum[i],dp[i]+sum[i]*sum[i]));
67             //printf("push:%d %d
",sum[i],dp[i]+sum[i]*sum[i]);
68         }
69         printf("%d
",dp[N]);
70     }
71 }