【bzoj1911】[Apio2010]特别行动队

输入

输出

样例输入

4
-1 10 -20
2 2 3 4

样例输出

9

题解

dp+斜率优化

设f[i]表示前i个士兵的战斗力之和的最大值。

那么有f[i]=f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c，，

其中sum为前缀和。

展开平方，整理得f[j]+a*sum[j]^2-b*sum[j]=2*a*sum[i]*sum[j]+f[i]-a*sum[i]^2-b*sum[i]-c。

这样就得到了y=kx+b的形式，而且要求的是其中b的最大值。

于是维护一个上凸包即可，与下凸包的差别就在于斜率比较时‘>‘和‘<‘的不同。

#include <cstdio> #define y(i) (f[i] + a * sum[i] * sum[i] - b * sum[i]) #define x(i) sum[i] long long sum[1000010] , f[1000010]; int q[1000010] , l , r; int main() { int n , i; long long a , b , c , x; scanf("%d%lld%lld%lld" , &n , &a , &b , &c); for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &x) , sum[i] = sum[i - 1] + x; for(i = 1 ; i <= n ; i ++ ) { while(l < r && y(q[l + 1]) - y(q[l]) > (x(q[l + 1]) - x(q[l])) * 2 * a * sum[i]) l ++ ; f[i] = f[q[l]] + a * (sum[i] - sum[q[l]]) * (sum[i] - sum[q[l]]) + b * (sum[i] - sum[q[l]]) + c; while(l < r && (y(i) - y(q[r])) * (x(q[r]) - x(q[r - 1])) > (x(i) - x(q[r])) * (y(q[r]) - y(q[r - 1]))) r -- ; q[++r] = i; } printf("%lld\n" , f[n]); return 0; }

【bzoj1911】[Apio2010]特别行动队