pid=3507">传送门

大意：打印一篇文章，连续打印一堆字的花费是这一堆的和的平方加上一个常数M。

首先我们写出状态转移方程 :f[i]=f[j]+(sum[i]−sum[j])2+M;

设 j 优于 k.

那么有 f[j]+(sum[i]−sum[j])2<f[k]+(sum[i]−sum[k])2

移项得出

(f[j]+sum[j]2)−(f[k]+sum[j]2)2∗(sum[j]+sum[k])<sum[i]

这就是一个非常理想的斜率式了。

#include<cstdio>

#include<cctype>

const int MAXN = 5 * 1e6;

void GET(int &n)

{

    char c, f=1;n=0;

    do{c=getchar(); if(c=='-')f=-1;}while(!isdigit(c));

    while(isdigit(c)){n = n *10 + c -'0'; c= getchar();}

    n = n * f;

}

int q[MAXN], f[MAXN], c[MAXN], s, t, n, m;

inline int Y(int j,int k)

{

    return f[j]+c[j]*c[j]-(f[k]+c[k]*c[k]);

}

inline int X(int j,int k)

{

    return 2*(c[j]-c[k]);

}

int main()

{

    while(~scanf("%d%d", &n,&m))

    {

        for(int i = 1; i <= n; i++)

        {

            GET(c[i]);

            c[i] += c[i-1];

        }

        s = 1, t = 0;

        q[++t] = 0;

        for(int i = 1; i <= n; i++)

        {

            while(s < t && Y(q[s+1], q[s]) <= c[i] * X(q[s+1], q[s])) ++ s;

            f[i] = f[q[s]] + m + (c[i] - c[q[s]])*(c[i] - c[q[s]]);

            while(s < t && X(q[t-1], q[t]) * Y(q[t], i) <= X(q[t], i) * Y(q[t-1], q[t])) -- t;

            q[++t] = i;

        }

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

    }

    return 0;

}