hdu 3507 Print Article(斜率优化DP)

题目链接：hdu 3507 Print Article

题意：

每个字有一个值，现在让你分成k段打印，每段打印需要消耗的值用那个公式计算，现在让你求最小值

题解：

设dp[i]表示前i个字符需要消耗的最小值，那么有dp[i]=min{dp[k]+(sum[i]-sum[k])²+m)}(k<i)。

这样是n² 的做法。

考虑用斜率优化：

设k<j,对于dp[i]，从k+1到i为一段比j+1到i为一段更优。

那么有

dp[j]+(sum[i]-sum[j])²+m<=dp[k]+(sum[i]-sum[k])²+m

整理得：

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

不等式的右边就是一个斜率，然后用单调队列优化，做到O(n)的复杂度。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

const int N=5e6+7;
int n,m,dp[N],sum[N],Q[N],head,tail;

int getx(int j,int k){return sum[j]-sum[k];}
int gety(int j,int k){return dp[j]+sum[j]*sum[j]-dp[k]-sum[k]*sum[k];}
int check(int i,int j,int k){return gety(i,j)*getx(j,k)<=gety(j,k)*getx(i,j);}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        F(i,1,n)scanf("%d",sum+i),sum[i]+=sum[i-1];
        head=1,tail=0;
        Q[++tail]=0;
        F(i,1,n)
        {
            while(head<tail&&gety(Q[head+1],Q[head])<=2*sum[i]*getx(Q[head+1],Q[head]))head++;
            dp[i]=dp[Q[head]]+(sum[i]-sum[Q[head]])*(sum[i]-sum[Q[head]])+m;
            while(head<tail&&check(i,Q[tail],Q[tail-1]))tail--;
            Q[++tail]=i;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}