Acw335.特别行动队
题意:
有$n$个士兵,编号为$1$到$n$,将它们拆分成若干个特别行动队调入战场。
同一支特别行动队的队员编号应该连续。
设士兵$i$的初始战斗力为$x_i$,一支特别行动队的战斗力为队内所有队员初始战斗力之和。
同时一支特别行动队的初始战斗力$x$会按照如下的公式修正为$x’$:
$$
x’=ax^2+bx+c
$$
$a,b,c$已知且$a<0$。
求修正后的战斗力之和的最大值。
数据范围$:n\leq 1e6$
思路:
首先对$x_i$求一个前缀和,这样就可以快速的计算某个段的初始战斗力以及修正后的战斗力的值。
设$f(i)$表示考虑到第$i$个数字,此时的结果为多少。
转移方程也比较好设计:
$$
f(i)=max\{f(j),g(j+1,i)\}
$$
其中$j\in [1,i-1]$,$g(i,j)$表示$i$到$j$这一段的修正后的战斗力的值。
此时算法复杂度为$O(n^2)$,无法通过,考虑优化。
把$g$函数展开。
$$
f(i)=max\{f(j)+a[s(i)-s(j)]^2+b(s(i)-s(j))+c )\}\\f(i)=max\{f(j)+as(i)^2+as(j)^2-2as(i)s(j)+bs(i)-bs(j)+c\}
$$
其中$s$函数表示前缀和函数。
去掉$max$:
$$
\{f(j)+as(j)^2-bs(j)\}=[2as(i)]s(j)+\{f(i)-as(i)^2-bs(i)-c\}
$$
这时候就很明显了,方程表达式为以$2as(i)$为斜率,$\{f(i)-as(i)^2-bs(i)-c\}$为截距,$s(j)$为自变量,$f(j)+as(j)^2-bs(j)$为因变量的直线。
又因为$a<0$所以他的斜率是负的,如果想让$f(i)$取到最大所以截距也要最大。
所以我们维护一个上凸壳。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e6+10;
int x[maxn];
int q[maxn];
ll s[maxn];
ll a, b, c;
ll f[maxn];
ld slope(int n, int m)
{
ld dx = (ld)s[n]-(ld)s[m];
ld dy = (ld)f[n]+(ld)a*(ld)s[n]*(ld)s[n]-(ld)b*(ld)s[n];
dy -= ((ld)f[m]+(ld)a*(ld)s[m]*(ld)s[m]-(ld)b*(ld)s[m]);
return dy/dx;
}
int main()
{
int n;
scanf("%d", &n);
cin >> a >> b >> c;
for(int i = 1; i <= n; i++)
{
scanf("%d", &x[i]);
s[i] = s[i-1]+x[i];
}
int hh = 1, tt = 1;
for(int i = 1; i <= n; i++)
{
while(hh < tt && slope(q[hh], q[hh+1]) >= 2.0*(ld)a*(ld)s[i]) hh++;
int j = q[hh];
f[i] = f[j]+a*(s[i]-s[j])*(s[i]-s[j])+b*(s[i]-s[j])+c;
while(hh < tt && slope(q[tt], i) >= slope(q[tt], q[tt-1])) tt--;
q[++tt] = i;
}
cout << f[n] << endl;
return 0;
}