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

Problem

【APIO2010】特别行动队

$\mathrm{Time\;Limit:\;4\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description


Input


Output


Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

标签：斜率优化DP

Solution

首先易得$\mathrm{DP}$方程：设$f[i]$为考虑前$i$人的最大收益，则$f[i]=\max_{j=0}^{i-1}\lbrace{A\times(S_i-S_j)^2+B\times(S_i-S_j)+C+f[j]}\rbrace$。
那么推一推：

$$\begin{aligned} f[i]&=\max_{j=0}^{i-1}\lbrace{A\times(S_i-S_j)^2+B\times(S_i-S_j)+C+f[j]}\rbrace\\ &=\max_{j=0}^{i-1}\lbrace{A\times S_i^2-A\times S_j^2+2A\times S_i\times S_j+B\times S_i-B\times S_j+C+f[j]}\rbrace\\ &=\max_{j=0}^{i-1}\lbrace{-2AS_j\times S_i+(A\times S_j^2-B\times S_j+f[j])}\rbrace+A\times S_i^2+B\times S_i+C\\ \end{aligned}$$

发现中间$-2AS_j\times S_i+(A\times S_j^2-B\times S_j+f[j])$是一次函数，那么对于两个位置$p,q\;(p<q)$，若$q$比$p$优秀，则有：

$$\begin{aligned} Let\;k_p=-2AS_p,\;b_p&=A\times S_p^2-B\times S_p+f[p]\\ k_pS_i+b_p&< k_qS_i+b_q\\ S_i&\le\frac{b_p-b_q}{k_q-k_p} \end{aligned}$$

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

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;
}