BZOJ3675【APIO2014】序列分割 <斜率优化>

Problem

【APIO2014】序列分割

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

$\mathrm{小H}$最近迷上了一个分隔序列的游戏。
在这个游戏里，$\mathrm{小H}$需要将一个长度为$n$的非负整数序列分割成$k+1$个非空的子序列。
为了得到$k+1$个子序列，$\mathrm{小H}$需要重复$k$次以下的步骤：

1. $\mathrm{小H}$首先选择一个长度超过$1$的序列（一开始$\mathrm{小H}$只有一个长度为$n$的序列，也就是一开始得到的整个序列）
2. 选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列

每次进行上述步骤之后，$\mathrm{小H}$将会得到一定的分数。这个分数为两个新序列中元素和的乘积。
$\mathrm{小H}$希望选择一种最佳的分割方式，使得$k$轮之后，$\mathrm{小H}$的总得分最大。

Input

输入第一行包含两个整数$n,k\;(k+1\le n)$。
第二行包含$n$个非负整数$a_1,a_2,\cdots,a_n\;(0\le a_i\le10^4)$，表示一开始$\mathrm{小H}$得到的序列。

Output

输出第一行包含一个整数，为$\mathrm{小H}$可以得到的最大分数。

Sample Input

7 3
4 1 3 4 0 2 3

Sample Output

108

Hint

在样例中，$\mathrm{小H}$可以通过如下3轮操作得到108分：

1. 一开始$\mathrm{小H}$有一个序列$(4,1,3,4,0,2,3)$。$\mathrm{小H}$选择在第$1$个数之后的位置将序列分成两部分，并得到$4\times (1+3+4+0+2+3)=52$分。
2. 这一轮开始时$\mathrm{小H}$有两个序列：$(4),\;(1,3,4,0,2,3)$。$\mathrm{小H}$选择在第3个数字之后的位置将第二个序列分成两部分，并得到$(1+3)\times(4+0+2+3)=36$分。
3. 这一轮开始时$\mathrm{小H}$有三个序列：$(4),\;(1,3),\;(4,0,2,3)$。$\mathrm{小H}$选择在第$5$个数字之后的位置将第三个序列分成两部分，并得到$(4+0)\times(2+3)=20$分。

经过上述三轮操作，$\mathrm{小H}$将会得到四个子序列：$(4),\;(1,3),\;(4,0),\;(2,3)$并总共得到$52+36+20=108$分。

标签：斜率优化DP

Solution

易得$\mathrm{DP}$方程：$f[t][i]$表示玩$t$轮时只考虑$[1,i]$区间内的数的最大贡献。那么有$f[t][i]=\max_{j=0}^{i-1}\lbrace{f[t-1][j]+(S_i-S_j)\times S_j}\rbrace$。
简单推一推：

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

套上斜率优化：

$$For\;i\in[1,n],\;if\;p<q,\;q\;is\;better\;than\;p,\;then\\ S_pS_i+f[t-1][p]-S_p^2\le S_qS_i+f[t-1][q]-S_q^2\\ Let\;a_n=S_n,\;b_n=f[t-1][n]-S_n^2,\\ then\;(a_p-a_q)S_i\le b_q-b_p\\ \therefore If\;(a_p-a_q)S_i\le b_q-b_p,\;then\;we\;can\;pop\;p\;out\;of\;the\;stack.$$

注意这里不要写成斜率的形式，因为$a_p-a_q$可能等于$0$。
按照不等式用单调栈对每层$k$进行维护即可，这里可以做$k$次一维$\mathrm{DP}$，每次重新算$b$数组。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
typedef long long lnt;
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, m, l, r, que[MAX_N+5]; lnt s[MAX_N+5];
lnt f[MAX_N+5], a[MAX_N+5], b[MAX_N+5];
bool chk(int p, int l, int r) {
    lnt x = (b[p]-b[que[r]])*(a[que[r-1]]-a[que[r]]);
    lnt y = (b[que[r]]-b[que[r-1]])*(a[que[r]]-a[p]);
    return x <= y;
}
int main() {
    read(n), read(m);
    for (int i = 1, x; i <= n; i++)
        read(x), s[i] = s[i-1]+x;
    for (int i = 1; i <= n; i++)
        a[i] = s[i], b[i] = -s[i]*s[i];
    for (int k = 1; k <= m; k++) {
        que[l = r = 0] = 0;
        for (int i = 1; i <= n; i++) {
            while (l < r && s[i]*(a[que[l]]-a[que[l+1]]) <= b[que[l+1]]-b[que[l]]) l++;
            f[i] = a[que[l]]*s[i]+b[que[l]]; while (l < r && chk(i, l, r)) r--; que[++r] = i;
        }
        for (int i = 1; i <= n; i++) b[i] = f[i]-s[i]*s[i];
    }
    return printf("%lld\n", f[n]), 0;
}