Print Article

题目链接：https://vjudge.net/problem/HDU-3507#author=0

题意：给出n个数，要求按顺序全部取出，每次取出一段所花费的费用为取出一段数的和的平方加m，问最小费用是多少。

思路：很容易想到一个O(n²)的做法，dp[i]=dp[j]+(sum[i]-sum[j])²+m；但n有5*10⁵，肯定会超时。这是就要进行化简了。

可以假设在求dp[i]是，dp[i]由dp[j]转换而来比由dp[k]转换来更优，（j>k）。

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

化简得(dp[j]+sum[j]²)-(dp[k]+sum[k]²)/(2*(sum[j]-sum[k]))<=sum[i]

如果上试成立的话，那j点就比k点更优，可以把k点淘汰掉。

令：yj=dp[j]+sum[j]*sum[j]   xj=2*sum[j]

（yj-yk）/(xj-xk) <= sum[i];

令g[k,j]=(yj-yk)/(xj-xk)

如果对于k<j<i，g[k,j]>g[j,i] 那么 j 也是可以淘汰的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[500005],sum[500005],q[500005];
ll getx(ll x)
{
    return 2*sum[x];
}
ll gety(ll x)
{
    return dp[x]+sum[x]*sum[x];
}
bool cross(ll x1,ll y1,ll x2,ll y2,ll x3,ll y3)
{
    ll ans=(y3-y1)*(x2-x1)-(y2-y1)*(x3-x1);
    if(ans<=0ll)
        return true;
    return false;
}
bool fun(ll x,ll y,ll i)
{
    if( (dp[x]+sum[x]*sum[x])-(dp[y]+sum[y]*sum[y]) <=2*sum[i]*(sum[x]-sum[y]) )
        return true;
    return false;
}
int main()
{
    ll n,m;
    while(~scanf("%lld%lld",&n,&m))
    {
        for(int i=1; i<=n; i++)
        {
            ll x;
            cin>>x;
            sum[i]=sum[i-1]+x;
            dp[i]=0;
        }
        int head=0,tail=1;
        q[0]=0;
        for(int i=1; i<=n; i++)
        {
            while((head+1<tail)&&fun(q[head+1],q[head],i))
                head++;
            ll x=q[head];
            dp[i]=dp[x]+(sum[i]-sum[x])*(sum[i]-sum[x])+m;
            while((head+1<tail)&&cross(getx(q[tail-2]),gety(q[tail-2]),getx(q[tail-1]),gety(q[tail-1]),getx(i),gety(i)) )
                tail--;
            q[tail++]=i;
        }
        cout<<dp[n]<<endl;
    }
}