题面在这里

题意

你有一支由(n)名预备役士兵组成的部队，士兵从(1)到(n)编号，要将他们拆分 成若干特别行动队调入战场。
出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如((i,i+1,…,i+k))的序列。
编号为(i)的士兵的初始战斗力为(x_i)，一支特别行动队的初始战斗力(x)为队内 士兵初始战斗力之和，即(x=x_i + x_{i+1} + … + x_{i+k})。
作为部队统帅，现在你要为这支部队进行编队，
使得所有特别行动队修正后战斗力之和最大。求出这个最大和。

数据范围

[1 ≤ n ≤ 1,000,000，–5 ≤ a ≤ –1，|b| ≤ 10,000,000，|c| ≤ 10,000,000，1 ≤ xi ≤ 100]

sol

似乎仍然是一道斜率DP入门题
我们设(f[i])表示选择前(i)名的修正战斗力最大值，那么有
[f[i]=max_{j=0}^{i-1}(f[j]+atimes(sum_{k=j+1}^{i}x[i])^2+btimes(sum_{k=j+1}^{i}x[i])+c)]
令(s[i]=(sum_{j=1}^{i}x[i]))，有
[f[i]=max_{j=0}^{i-1}(f[j]+a(s[i]-s[j])^2+b(s[i]-s[j])+c)]
[=max_{j=0}^{i-1}(f[j]-btimes s[j]+atimes s[j]^2-2atimes s[i]s[j])]
[+atimes s[i]^2+btimes s[i]+c]
由于(a<0)，故插点((2atimes s[j],f[j]-btimes s[j]+atimes s[j]^2))，
询问递增斜率(k_i=s[i])即可

只是维护的是第三象限的上凸包!!!

代码

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mp make_pair
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=1e8;
const int N=1000010;
il ll read(){RG ll data=0,w=1;RG char ch=getchar();while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();return data*w;
}il void file(){freopen(".in","r",stdin);freopen(".out","w",stdout);
}ll n,a,b,c,s[N],f[N],L=N,R=N-1;struct node{ll x,y;}Q[N];
//队列改啦!!!
il void insert(node q){while(L<R&&(Q[L+1].y-Q[L].y)*(Q[L].x-q.x)>=(Q[L].y-q.y)*(Q[L+1].x-Q[L].x))L++;Q[--L]=q;
}il ll query(ll k){while(L<R&&k*(Q[R].x-Q[R-1].x)>=Q[R].y-Q[R-1].y)R--;return Q[R].y-k*Q[R].x;
}int main()
{n=read();a=read();b=read();c=read();for(RG int i=1;i<=n;i++)s[i]=read()+s[i-1];insert((node){0,0});for(RG int i=1;i<=n;i++){f[i]=query(s[i])+a*s[i]*s[i]+b*s[i]+c;insert((node){2*a*s[i],f[i]-b*s[i]+a*s[i]*s[i]});}printf("%lldn",f[n]);return 0;
}

转载于:https://www.cnblogs.com/cjfdf/p/8659835.html