【题解】 P3628 [APIO2010]特别行动队（斜率优化）

巴菲特 · 2021-03-17 21:29:37 · 个人记录

思路

斜率的单调性——递增or递减

注意到斜率k是递减的，所以维护的实际上是一个斜率不断减小的凸壳，队头元素的斜率是最大的，一些斜率太大的点就要出队，而入队的条件是新的斜率要比队尾斜率小。这两点在while()中注意一下就好了。

代码

#include<bits/stdc++.h>
#define ll long long
#define QzQ 0
#define db double
using namespace std;
int n, x, a, b, c;
int hd, tl, que[1000010];
ll sum[1000010], suma[1000010], sumb[1000010], f[1000010];
struct Pot{
    ll x, y;
    void NewPot(int i){
        x = sum[i]; y = f[i] + suma[i] - sumb[i];
    }
}pt[1000010];
db slope(int j, int i){
    return (1.0 * pt[i].y - pt[j].y ) / (1.0 * pt[i].x - pt[j].x);
}
ll get(int j, int i){
    return f[j] + suma[i] + suma[j] - 2*a*sum[i]*sum[j] + sumb[i] - sumb[j] + c;
}
int main(){
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &x);
        sum[i] = sum[i - 1] + x;
        suma[i] = sum[i] * sum[i] * a;
        sumb[i] = sum[i] * b;
    }
    hd = tl = 1;
    for(int i = 1; i <= n; ++i){
        while(hd < tl && slope(que[hd], que[hd + 1]) >= 2.0 * a * sum[i]) hd++;
        f[i] = get(que[hd], i);
        pt[i].NewPot(i);
        while(hd < tl && slope(que[tl - 1], que[tl]) <= slope(que[tl], i))  tl--;
        que[++tl] = i; 
    }
    printf("%lld\n", f[n]);
}