[bzoj1911][Apio2010特别行动队] (动态规划+斜率优化)

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4 

Sample Output

9

HINT

Solution

斜率优化动态规划

首先易得出这样的一个朴素状态转移方程

f[i]=max{f[j]+cal(sum[i]-sum[j])}

其中j<i，且cal(x)=a*x*x+b*x+c

那么设转移方程中的式子为V

若i<j，且V(j)>V(i)

那么，f[j]-f[i]+a*sum[j]^2-a*sum[i]^2+b*(sum[i]-sum[j])>2*a*(sum[j]-sum[i])*sum[i]

就可以斜率优化了

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1000010;
typedef long long ll;
inline ll sq(ll x){
  return x*x;
}
inline int read(){
  int x=0,c=getchar(),f=1;
  for(;c<48||c>57;c=getchar())
    if(!(c^45))
      f=-1;
  for(;c>47&&c<58;c=getchar())
    x=(x<<1)+(x<<3)+c-48;
  return x*f;
}
int n,a,b,c,q[N];
ll sum[N],f[N];
inline double slope(int x,int y){
  return (double)(f[y]-f[x]+a*(sq(sum[y])-sq(sum[x]))+b*(sum[x]-sum[y]))/(double)(2*a*(sum[y]-sum[x]));
}
int main(){
  n=read(),a=read(),b=read(),c=read();
  for(int i=1;i<=n;i++)
    sum[i]=(ll)read()+sum[i-1];
  int l=0,r=0;
  for(int i=1;i<=n;i++){
    while(l<r&&slope(q[l],q[l+1])<sum[i])l++;
    int t=q[l];
    f[i]=f[t]+a*sq(sum[i]-sum[t])+b*(sum[i]-sum[t])+c;
    while(l<r&&slope(q[r-1],q[r])>slope(q[r],i))r--;
    q[++r]=i;
  }
  printf("%lld
",f[n]);
  return 0;
}

orz hzwer