本文共 2011 字，大约阅读时间需要 6 分钟。

题意

$n$名士兵,你需要把士兵分成连续的一段一段特别行动队

设其中一队的战斗力和为$x$,那么修正战斗力是$a{x}^2+bx+c$(当然$a<0$)

求一种分组方式,使得修正战斗力之和最大

转移方程为

$$f[i]=f[j]+a\ast (su{m}_i-su{m}_j{)}^2+b\ast (su{m}_i-su{m}_j)+c$$

$$f[i]=f[j]+a\ast su{m}_i^2+a\ast su{m}_j^2-2a\ast su{m}_i\ast su{m}_j+b\ast su{m}_i-b\ast su{m}_j+c$$

$$2a\ast su{m}_i\ast su{m}_j+f[i]-a\ast su{m}_i^2-b\ast su{m}_i-c=f[j]+a\ast su{m}_j^2-b\ast su{m}_j$$

把$2\ast a\ast su{m}_i$看作斜率,$su{m}_j$看作自变量$x$,等式右边看作$y$

那么就是要最大化截距,维护一个上凸壳

当$slope(q_{head},q_{head+1})>2\ast a\ast su{m}_i$时,$head++$

然后用队头更新$f[i]$

我们加入点$i$也需要维护上凸壳的斜率单调性

若$slope(q_{tail-1},q_{tail})>=slope(q_{tail,i})$说明在上凸壳上,否则就踢出队列

#include 
   
    using namespace std;#define int long longconst int maxn = 1e6+10;int n,a,b,c,sum[maxn],f[maxn];int head = 1, tail = 0, q[maxn];int x(int i){
    return sum[i]; }int y(int i){
    return f[i]+a*sum[i]*sum[i]-b*sum[i]; }double slope(int i,int j){
   	return ( 1.0*y(i)-y(j) )/( 1.0*x(i)-x(j) );}signed main(){
   	cin >> n >> a >> b >> c ;		for(int i=1;i<=n;i++)	cin >> sum[i];	for(int i=1;i<=n;i++)	sum[i] += sum[i-1];	q[++tail] = 0;	for(int i=1;i<=n;i++)	{
   		while( head+1<=tail && slope(q[head],q[head+1])>2*a*sum[i] )	head++;		int las = q[head];		f[i] = f[las]+a*sum[i]*sum[i]+a*sum[las]*sum[las]-2*a*sum[i]*sum[las]+b*sum[i]-b*sum[las]+c;		while( tail-1>=head && slope(q[tail-1],q[tail])<=slope(q[tail],i) )	tail--;		q[++tail] = i;	}	cout << f[n];}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116272325 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！