BZOJ1911【APIO2010】特别行动队 <斜率优化>

Problem

【APIO2010】特别行动队

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

标签：斜率优化DP

Solution

首先易得方程：设为考虑前人的最大收益，则。
那么推一推：

发现中间是一次函数，那么对于两个位置，若比优秀，则有：

按照此斜率维护单调栈即可。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
typedef long long lnt;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, que[MAX_N+5], l, r; lnt A, B, C;
lnt s[MAX_N+5], k[MAX_N+5], b[MAX_N+5], f[MAX_N+5];
dnt calc(int x, int y) {return (dnt)(b[x]-b[y])/(dnt)(k[y]-k[x]);}
int main() {
    read(n), read(A), read(B), read(C);
    for (int i = 1, x; i <= n; i++)
        read(x), s[i] = s[i-1]+x;
    int l = 0, r = 0; que[0] = 0, b[0] = C;
    for (int i = 1; i <= n; i++) {
        while (l < r && calc(que[l], que[l+1]) <= s[i]) l++;
        f[i] = k[que[l]]*s[i]+b[que[l]]+A*s[i]*s[i]+B*s[i];
        k[i] = -2*A*s[i], b[i] = A*s[i]*s[i]-B*s[i]+C+f[i];
        while (l < r && calc(que[r], i) <= calc(que[r-1], que[r])) r--;
        que[++r] = i;
    }
    return printf("%lld\n", f[n]), 0;
}