[Apio2010]特别行动队
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
这是道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;
}
评论 (0)
