BZOJ1911 特别行动队

目录

• BZOJ1911 特别行动队
• 题解
• ｃｏｄｅ

BZOJ1911 特别行动队

题目传送门

题解

典型的斜率优化(Dp)。首先如果我们记(sum[i])表示前(i)个士兵的战斗力之和，那么我们比较容易的可以得出(O(n^2))的(Dp)：(f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c))。如果(k>j)并且(k)比(j)更优，那么可以得出：

$f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c

整理之后可得：

$frac{f[k]-f[j]+a*(sum[k]-sum[j])^2-b*(sum[k]-sum[j])}{2*a*(sum[k]-sum[j])}leq sum[i]$

然后就是用单调队列进行优化了。

ｃｏｄｅ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('
');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int maxn=2e6+500;
int n;
int a,b,c;
int x[maxn];
int l,r;
int que[maxn];
ll f[maxn],sum[maxn];
/*==================Define Area================*/
ll Sqr(ll x) {
	return x*x;
}

double Cal(int x,int y) {
	return (double)(f[y]-f[x]+a*(Sqr(sum[y])-Sqr(sum[x]))-b*(sum[y]-sum[x]))/(double)(2*a*(sum[y]-sum[x]));
}

int main() {
	read(n);
	read(a);read(b);read(c);
	for(int i=1;i<=n;i++) {
		read(x[i]);
	}
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+x[i];
	for(int i=1;i<=n;i++) {
		while(l<r&&Cal(que[l],que[l+1])<sum[i]) l++;
		int t=que[l];
		f[i]=f[t]+a*Sqr(sum[i]-sum[t])+b*(sum[i]-sum[t])+c;
		while(l<r&&Cal(que[r-1],que[r])>Cal(que[r],i)) r--;
		que[++r]=i;
	}
	printf("%lld
",f[n]);
	return 0;
}