【动态规划】斜率优化

https://codeforces.com/contest/320/problem/E
斜率优化dp

https://codeforces.com/contest/631/problem/E

单调栈维护一个决策凸包，二分。

int n;
ll a[200005];
ll sum[200005];
int Q[200005];
double K[200005];

ll ans;
ll basesum;

double calc(int i2, int i1) {
    return 1.0 * (sum[i2] - sum[i1]) / (i2 - i1);
}

double calc2(int i2, int i1) {
    return 1.0 * (sum[i2 - 1] - sum[i1 - 1]) / (i2 - i1);
}

void calcRight() {
    int r = 0;
    Q[++r] = 1;
    K[r] = -INF;
    for(int i = 2; i <= n; ++i) {
        while(r >= 1 && K[r] >= calc(i, Q[r]))
            --r;
        Q[++r] = i;
        K[r] = calc(Q[r], Q[r - 1]);
    }
    for(int i = 1; i <= n; ++i) {
        int pos = lower_bound(K + 1, K + 1 + r, 1.0 * a[i]) - K;
        for(int j = max(1, pos - 2); j <= min(r, pos + 2); ++j) {
            int J = Q[j];
            if(J <= i)
                continue;
            ll tmp = basesum - a[i] * i + sum[i] + a[i] * J - sum[J];
            cmax(ans, tmp);
        }
    }
}

void calcLeft() {
    int r = 0;
    Q[++r] = 1;
    K[r] = -INF;
    for(int i = 2; i <= n; ++i) {
        while(r >= 1 && K[r] >= calc2(i, Q[r]))
            --r;
        Q[++r] = i;
        K[r] = calc2(Q[r], Q[r - 1]);
    }
    for(int i = 1; i <= n; ++i) {
        int pos = lower_bound(K + 1, K + 1 + r, 1.0 * a[i]) - K;
        for(int j = max(1, pos - 2); j <= min(r, pos + 2); ++j) {
            int J = Q[j];
            if(J >= i)
                continue;
            ll tmp = basesum - a[i] * i + sum[i - 1] + a[i] * J - sum[J - 1];
            cmax(ans, tmp);
        }
    }
}