HDU3507_Print Article

这个题目又是一个典型的dp斜率优化的题目。题意是给你n个数，你需要做的是把这个n个数分为连续的若干段，每段的权值为这段数字的和的平方加上M。求最小的总权值。

我们可以根据题意写出朴素版的dp状态转移方程。然后就可以推导出使用优先队列来维护最优值。总共包括对首和队尾的两个操作。

很简单，很朴素的题目，直接上代码吧。。。。就是范围定义小了，然后Wa了n^n^n^n^……发。 深坑啊。。。

#include <iostream>

#include <cstdio>

#include <cstring>

#define maxn 500500

#define ll long long

using namespace std;

ll f[maxn],a[maxn],sum[maxn];

ll n,m,xx,yy,xx1,yy1;

ll q[maxn],head,tail;

ll dy(ll j1,ll j2) { return f[j2]+sum[j2]*sum[j2]-f[j1]-sum[j1]*sum[j1]; }

ll dx(ll j1,ll j2) { return *(sum[j2]-sum[j1]); }

int main()

{

    while (scanf("%I64d%I64d",&n,&m)!=EOF)

    {

        for (ll i=; i<=n; i++) scanf("%I64d",&a[i]),sum[i]=sum[i-]+a[i];

        head=tail=,q[]=;

        for (ll i=; i<=n; i++)

        {

            while (tail-head>)

            {

                xx=dx(q[head],q[head+]);

                yy=dy(q[head],q[head+]);

                if (sum[i]*xx>=yy) head++;

                    else break;

            }

            f[i]=f[q[head]]+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+m;

            while (tail-head>)

            {

                yy=dy(q[tail-],q[tail]);

                xx=dx(q[tail-],q[tail]);

                yy1=dy(q[tail],i);

                xx1=dx(q[tail],i);

                if (yy*xx1>=yy1*xx) tail--;

                    else break;

            }

            q[++tail]=i;

        }

        printf("%I64d\n",f[n]);

    }

    return ;

}