洛谷P3628 [APIO2010]特别行动队斜率优化-白红宇

洛谷P3628 [APIO2010]特别行动队斜率优化

阅读量：5281 次

发布时间：2019-06-14

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

裸题，注意队列下标不要写错

Code：

#include
     
      #include
      
       #include
       
        using namespace std;const int maxn = 2000000 + 3;long long f[maxn], sum[maxn], a, b, c;int n, q[maxn];inline double re_x(int i){ return sum[i]; };inline double re_y(int i){ return f[i] + a * sum[i] * sum[i] - b * sum[i]; }inline double re_slope(int i,int j){ return (re_y(i) - re_y(j)) / (re_x(i) - re_x(j)); }int main(){    freopen("input.txt","r",stdin);    scanf("%d",&n);    scanf("%lld%lld%lld",&a,&b,&c);    for(int i = 1;i <= n; ++i)scanf("%lld",&sum[i]), sum[i] += sum[i - 1];    int head = 0, tail = 0;    for(int i = 1;i <= n; ++i)    {        while(head < tail && re_slope(q[head], q[head + 1]) > sum[i] * 2 * a) ++ head;        f[i] = f[q[head]] + a * (sum[i] - sum[q[head]]) * (sum[i] - sum[q[head]]) + b * (sum[i] - sum[q[head]]) + c;        while(head < tail && re_slope(i, q[tail - 1])  >re_slope(q[tail - 1], q[tail])) -- tail;        q[++tail] = i;    }    printf("%lld",f[n]);    return 0;}