bzoj1911【APIO2010】特别行动队

bzoj1911【APIO2010】特别行动队

Description

Input

Output

Sample Input

Sample Output

HINT

Source

斜率优化DP

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 1000005
using namespace std;
int n,l,r;
ll a,b,c,q[maxn],f[maxn],s[maxn];
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
inline double getk(int x,int y)
{return (double)((f[x]+a*s[x]*s[x]-b*s[x])-(f[y]+a*s[y]*s[y]-b*s[y]))/(double)(s[x]-s[y]);
}
int main()
{n=read();a=read();b=read();c=read();F(i,1,n) s[i]=s[i-1]+read();l=r=1;q[1]=0;F(i,1,n){while (l<r&&getk(q[l],q[l+1])>a*s[i]*2) l++;f[i]=f[q[l]]+a*s[q[l]]*s[q[l]]-b*s[q[l]]-a*s[i]*s[q[l]]*2+a*s[i]*s[i]+b*s[i]+c;while (l<r&&getk(q[r-1],q[r])<getk(q[r],i)) r--;q[++r]=i;}printf("%lld\n",f[n]);return 0;
}