BZOJ1911：[Apio2010]特别行动队—

BZOJ1911：[Apio2010]特别行动队——题解

阅读量：6457 次

发布时间：2019-06-23

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

又是一个显然的dp……好吧我懒得讲了。

s[i]是战斗力前缀和。

我们仍然设k<j<i，化简一下得到f[j]-2*a*s[i]s[j]+a*s[j]^2-b*s[j]>f[k]-2*a*s[i]s[k]+a*s[k]^2-b*s[k]

于是得到：

0.5*(f[j]+a*s[j]*s[j]-b*s[j]-f[k]-a*s[k]*s[k]+b*s[k])/(a*(s[j]-s[k]))

显然可以斜率优化了。

（为什么变号，emmmmmm……a<0）

至于剩下的套路部分就请看这道题的解法吧。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;const int N=1000010;const ll INF=1e18;inline int read(){    int X=0,w=1;char ch=0;    while(ch<'0'||ch>'9'){
   if(ch=='-')w=-1;ch=getchar();}    while(ch>='0'&&ch<='9')X=(X<<1)+(X<<3)+ch-'0',ch=getchar();    return X*w;}int n,l,r;ll a,b,c;ll f[N],q[N],s[N];inline double suan(int k,int j){    return 0.5*(f[j]+a*s[j]*s[j]-b*s[j]-f[k]-a*s[k]*s[k]+b*s[k])/(a*(s[j]-s[k]));}int main(){    n=read(),a=read(),b=read(),c=read();    for(int i=1;i<=n;i++)s[i]=s[i-1]+read();    for(int i=1;i<=n;i++){        while(l
          
           <(double)s[i])l++; ll k=s[i]-s[q[l]]; f[i]=f[q[l]]+a*k*k+b*k+c; while(l