【bzoj1911】[Apio2010]特别行动队

1911: [Apio2010]特别行动队

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 4048 Solved: 1913
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

【题解】

首先很容易想到用前缀和，下面的sum表示前缀和。

然后写出状态转移方程：f[i]=max{f[j]+a(sum[i]-sum[j])^2+b(sum[i]-sum[j])+c}

假设j比k更优，得到斜率表达式(f[j]+a*sum[j]^2-b*sum[j])-(f[k]+a*sum[k]^2-b*sum[k])/(sum[j]-sum[k])>2a*sum[i]

然后斜率优化走起。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<algorithm>
 8 using namespace std;
 9 typedef long long ll;
10 #define MAXN 1000100
11 #define FILE "read"
12 #define up(i,j,n) for(ll i=j;i<=n;i++)
13 ll n,a,b,c,l,r,x[MAXN],sum[MAXN],q[MAXN],f[MAXN];
14 namespace INIT{
15     char buf[1<<15],*fs,*ft;
16     inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
17     inline ll read() {
18         ll x=0,f=1;  char ch=getc();
19         while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}        
20         while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
21         return x*f;
22     }
23 }using namespace INIT;
24 inline double slop(ll j,ll k) {return (double)((f[j]+a*sum[j]*sum[j]-b*sum[j])-(f[k]+a*sum[k]*sum[k]-b*sum[k]))/(double)(sum[j]-sum[k]);}
25 int main(){
26     freopen(FILE".in","r",stdin);
27     freopen(FILE".out","w",stdout);
28     n=read();  a=read();  b=read();  c=read();
29     up(i,1,n) x[i]=read(),sum[i]=sum[i-1]+x[i];
30     up(i,1,n){
31         while(l<r&&slop(q[l],q[l+1])>2*a*sum[i])  l++;
32         ll t=q[l];
33         f[i]=f[t]+a*(sum[i]-sum[t])*(sum[i]-sum[t])+b*(sum[i]-sum[t])+c;
34         while(l<r&&slop(q[r],i)>slop(q[r-1],q[r]))  r--;
35         q[++r]=i;
36     }
37     printf("%lld
",f[n]);
38     return 0;
39 }