[Apio2010]特别行动队

BZOJ1911
 
这是道DP斜率优化的模板题啊...
首先很容易得出朴素的DP状态转移方程如下:
f(i) = max{f(j) + g(S(i) - S(j))} (0 < j < i)
其中,g(x) = a*x^2 + b*x + c  ,  S(i) = Σ(k = 1,i)xk
展开、化简之后得:
f(i) = max(f(j) + a*S(j)^2 - b * S(j) - 2*a*S(i)*S(j)} + g(S(i))
 
令Y = f(j) + a*S(j)^2 - b*S(j)
令K = 2*a*S(i)
令X = S(j)
令C = g(S(i))
 
于是可得:
f(i) = max{Y - K*X} + C = max{B|B = Y - K*X} + C = max{B|Y = K*X + B} + C
其中,X,Y只与j和f(j)有关(二维向量(X,Y)随着f(j)的确定而被确定)
而C、K只与i有关(每个i对应了一个斜率)
因此每得到一个f(i),我们可以计算出其所对应的二位向量,并将其放入平面T内
当我们需要计算f(i)时,我们可以确定其所对应斜率,然后找到平面上的某个点,最大化过这点所确定的直线与y
轴交点的纵坐标
 
我们的求解顺序是:i-1总在i前求解,而xi > 0,因此X(也就是S(i))随着i递增,同样的我们可以得到K随着i递减
K的单调性意味着决策的单调性:若二维向量P是状态i的最优决策,那么状态i+1的最优决策的横坐标一定大于等于P
的横坐标,因此由此可以设计一个O(n)的算法,即每次转移时从上一个最优决策开始枚举当前决策,每个平面上的点被枚举到的次数之和不会超过2*n次,均摊O(1),n次转移,因此时间复杂度为O(n)
 
完整代码如下:

#include <stdio.h>

#include <iostream>

 

typedef long long Long;

 

Long a = 0;

Long b = 0;

Long c = 0;

int n = 0;

 

struct poi

{

    Long x;

    Long y;

    poi(Long X,Long Y)

    {

        x = X;

        y = Y;

    }

    poi()

    {}

};

 

const int N = 1000000;

 

Long S[N + 100];

Long f[N + 100];

poi pois[N + 100];

int num_p = 0;//num_p:栈顶

int now_p = 0;//now_p:你现在选的话就选它

 

Long g(Long x)

{

    return a * x * x + b * x + c;

}

 

Long get_ll()

{

    Long sym = 1LL;

    Long r = 0LL;

    char c = 0;

    do

    {

        c = getchar();

    }

    while(c == ' ' || c == '\n' || c == '\t');

     

    if(c == '-')

    {

        sym = -1LL;

        c = getchar();

    }

     

    do

    {

        r *= 10LL;

        r += (Long)(c - '0');

        c = getchar();

    }

    while(c >= '0' && c <= '9');

     

    return sym * r;

}

int main()

{

 

    scanf("%d",&n);

 

    a = get_ll();

    b = get_ll();

    c = get_ll();

     

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

    {

        S[i] = S[i - 1] + get_ll();

    }

 

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

    {

        if(num_p > now_p)

        {

            Long k = 2LL * a * S[i];

            Long now_b = -(1LL << 59);

            for(int j = now_p;j < num_p;j++)

            {

                if((pois[j].y - k * pois[j].x) > now_b)

                {

                    now_b = (pois[j].y - k * pois[j].x);

                    now_p = j;

                }

            }

            if(now_b > 0LL)

                f[i] += now_b;

        }

 

        f[i] += g(S[i]);

         

        pois[num_p++] = poi(S[i],f[i] + a * S[i] * S[i] - b * S[i]);

    }

 

    std::cout<<f[n]<<std::endl;

 

    return 0;

}