[HDU 3507]Print Article

Description

Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost

M is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

Input

There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.

Output

A single number, meaning the mininum cost to print the article.

Sample Input

5 5

5

9

5

7

5

Sample Output

230

题目大意

将一个序列分为若干段，每段代价为该段和平方+常数M，求代价和最小。

题解

斜率优化$DP$。

考虑朴素的做法，我们令$f[i]$表示前$i$位的最小代价和。

显然我们有转移方程：

f[i]=f[j]+sqr(sum[i]-sum[j])+m; //j>0&&j<i,sum[i]=∑a[i]

显然这是一个$O(n^2)$的做法，对于$500000$的数据肯定过不去。

可以发现，我们枚举每个$i$时会不断重复遍历相同的元素，显然冗余的遍历是可以略去的。

用数据结构优化，为了找到最值，我们容易想到单调队列。

由刚才那个式子，我们拆开：

f[i]=f[j]+sqr(sum[i]-sum[j])+m
<=>f[i]=f[j]+sqr(sum[i])+sqr(sum[j])-2*sum[i]*sum[j]+m
<=>f[i]=  f[j]+sqr(sum[j])+m  +sqr(sum[i])-2*sum[i]*sum[j] (*)

我们发现$(*)$式的右边的前面一个部分是与$i$无关的，可是后面一个部分，即

-2*sum[i]*sum[j]

中的$i$,$j$杂糅在了一起，显然普通的单调队列行不通了。

我们令$k<j<i$，假设计算$f[i]$时，$j$处的值比$k$处优，显然我们会有：

f[j]+sqr(sum[i]-sum[j])+M <= f[k]+sqr(sum[i]-sum[k])+M;

拆开，化简：

((f[j]+sum[j]*sum[j])-(f[k]+sum[k]*sum[k])) / 2(sum[j]-sum[k]) <=sum[i]

这时，我们发现，式子只有右边与$i$有关了，我们可以考虑拿左边的部分放到队列里面。

我们不妨令

yj=(f[j]+sum[j]*sum[j]),yk=(f[k]+sum[k]*sum[k]),xj=2*sum[j],xk=2*sum[k]
Δy=yj-yk，Δx=xj-xk

那么就变成了斜率表达式：

Δy/Δx <= sum[i];

而且不等式右边是递增的。

所以我们可以看出以下两点：我们令

g[k,j]=Δy/Δx

第一：如果上面的不等式成立，那就说$j$比$k$优，而且随着$i$的增大上述不等式一定是成立的，也就是对$i$以后算$DP$值时，j都比k优。那么$k$就是可以淘汰的。

第二：如果，$k<j<i$，而且$g[k,j]>g[j,i]$那么$j$是可以淘汰的。

假设：$g[j,i]<sum[i]$就是$i$比$j$优，那么$j$没有存在的价值

相反如果：$g[j,i]>sum[i]$，那么同样有，$g[k,j]>sum[i]$ ，那么$k$比$j$优那么$j$是可以淘汰的，所以这样相当于在维护一个下凸的图形，斜率在逐渐增大。

通过一个单调队列来维护下凸壳。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
#define RE register
#define IL inline
#define sqr(x) (x*x)
#define deltax(j,k) (2*(sum[j]-sum[k]))
#define deltay(j,k) ((f[j]+sqr(sum[j]))-(f[k]+sqr(sum[k])))
using namespace std;
const int N=500000;

IL int Read();

int n,m;
int sum[N+5];
int q[N+5],head,tail;
int f[N+5];

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        for (RE int i=1;i<=n;i++) sum[i]=sum[i-1]+Read(),f[i]=0;
        head=tail=0;
        q[tail++]=0;
        for (RE int i=1;i<=n;i++)
        {
            while (head<tail-1)
                if (deltay(q[head+1],q[head])<=sum[i]*deltax(q[head+1],q[head])) head++;
                else break;
            int x=sum[i]-sum[q[head]];
            f[i]=f[q[head]]+sqr(x)+m;
            while (head<tail-1)
                if (deltay(q[tail-1],q[tail-2])*deltax(i,q[tail-1])>=deltax(q[tail-1],q[tail-2])*deltay(i,q[tail-1])) tail--;
                else break;
            q[tail++]=i;
        }
        printf("%d
",f[n]);
    }
    return 0;
}

IL int Read()
{
    int sum=0;
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}