HDU3507-Print Article-斜率dp入门题

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

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

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

代码学的上面 很模板

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 //typedef long long LL;

 struct Point{

     int x,y;

     Point (int _x=,int _y=):x(_x),y(_y){}

     Point operator - (const Point &rhs) const

     {

         return Point(x-rhs.x,y-rhs.y);

     }

 };

 typedef Point Vector;

 inline int Cross(const Vector &u,const Vector &v)

 {

     return u.x*v.y - u.y*v.x;

 }

 const int maxn = 5e5+;

 int N,M;

 int sum[maxn],save[maxn];

 int dp[maxn];

 struct dequeue{

     Point q[maxn];

     int head,tail;

     void init()

     {

         head = ;tail = ;

         //q[head].x = 0;q[head].y = 0;

     }

     void push(const Point &u)

     {

         while(head < tail && Cross(q[tail]-q[tail-],u-q[tail])<=) tail--;

         q[++tail] = u;

     }

     Point pop(const int &k)

     {

         while(head < tail && k*q[head].x+q[head].y >= k*q[head+].x + q[head+].y) head++;

         //printf("head:%d x:%d y:%d\n",head,q[head].x,q[head].y);

         return q[head];

     }

 }H;

 int main()

 {

     //freopen("input.txt","r",stdin);

     while(~scanf("%d%d",&N,&M))

     {

         sum[] = ;

         for(int i=;i<=N;i++)

         {

             scanf("%d",&save[i]);

             sum[i] = sum[i-]+save[i];

         }

         H.init();

         H.push(Point(,));

         dp[] = ;

         for(int i=;i<=N;i++)

         {

             int k = -*sum[i];

             Point u = H.pop(k);

             //printf("i:%d k:%d u.x:%d u.y:%d\n",i,k,u.x,u.y);

             dp[i] = u.x*k + u.y + sum[i]*sum[i] + M;

             H.push(Point(sum[i],dp[i]+sum[i]*sum[i]));

             //printf("push:%d %d\n",sum[i],dp[i]+sum[i]*sum[i]);

         }

         printf("%d\n",dp[N]);

     }

 }