【bzoj1911】【APIO2010】【特别行动队】【斜率优化】
发布日期:2021-11-16 15:38:15 浏览次数:1 分类:技术文章

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

HINT

题解:写出dp方程之后斜率优化即可。维护一个上凸壳。

代码:

#include<iostream>#include<cstdio>#define N 1000100using namespace std;int q[N],n,h(1),t(1);long long a,b,c,sum[N],f[N],v[N];long long pow(long long x){return x*x;}long long G(int x,int y){return f[x]-f[y]+a*(pow(sum[x])-pow(sum[y]))+b*(sum[y]-sum[x]);}long long S(int x,int y){return a*(sum[x]-sum[y]);}double cal(int x,int y){return (G(x,y)*1.0)/(S(x,y)*2.0);}int main(){  scanf("%d",&n);scanf("%lld%lld%lld",&a,&b,&c);  for (int i=1;i<=n;i++){scanf("%lld",&v[i]);sum[i]=sum[i-1]+v[i];}  for (int i=1;i<=n;i++){    while (h<t&&sum[i]>cal(q[h+1],q[h]))h++;    f[i]=f[q[h]]+a*pow(sum[i]-sum[q[h]])+b*(sum[i]-sum[q[h]])+c;    while (h<t&&cal(i,q[t])<cal(q[t],q[t-1])) t--;    q[++t]=i;   }   cout<<f[n]<<endl;}


上一篇:【bzoj1010】【HNOI2008】【玩具装箱toy】【斜率优化】
下一篇:【bzoj1096】【ZJOI2007】【仓库建设】【斜率优化dp】