「APIO2014」序列分割「斜率优化」
hongzy
2018-12-27 18:50:52
首先,这题**答案与切的顺序无关**
证明很好证,考虑将一块$abc$分为$a,b,c$三块
方法一:先分成$a,bc$。答案为$a (b + c) + bc = ab + ac + bc$
方法二:先分成$ab,c$。答案为$c (a + b) + ab = ab + ac + bc$
答案相同。
然后考虑$dp$方程:若$s[x]=\sum_{i=1}^x a[i]$,令$f[i][j]$表示前$i$个数分$j$次的最大得分
$f[i][j]=min_{0\leq l<i}(f[l][j - 1] + s[l] * (s[i] - s[l]))$
需要滚动数组存,以下用$f[i]$表示$f[i][j-1]$(前驱状态)
然后考虑当$i$选$j$转移优于$l$时:(以下默认$j < l$)
$$f[j] + s[j]s[i] - s[j]^2 > f[l] + s[l]s[i] - s[l]^2$$
$$f[j] - s[j]^2 - (f[l] - s[l]^2) > (s[l]- s[j])s[i]$$
$$\frac{f[j] - s[j]^2 - (f[l] - s[l]^2)}{- s[j] -(-s[l])} > s[i]$$
把每个点看做$P_i(-s[i],f[i]-s[i]^2)$,那么单调队列维护一个点集,斜率递增
这些点形成了一个在第三象限的下凸包
操作:
队头更新:若$slope(q[head], q[head + 1]) \leq s[i]$则出队(显然)
队尾更新:若$slope(q[back - 1], q[back]) \geq slope(q[back], i)$则出队
**队尾操作的证明**(也就是**对凸包的证明**):
考虑$q[back]$可不可能做队头。若满足刚刚上方的条件,则:
若$slope(q[back],q[back-1]) \leq s[i]$使得$q[back]$成了队首
这时候当前的$slope$比刚刚的还要小,因此将继续出队,$q[back]$无法做队头。
斜率递增,故是一个凸包
还有一个细节:注意可能会出现$a[i]=0$,导致存在$s[i] = s[j]$,因此计算斜率应注意横坐标相同的情况,斜率为$-\infty$.
```cpp
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k, fa[205][N];
LL s[N], f[N], g[N];
double slope(int a, int b) {
LL x1 = - s[a], y1 = g[a] - s[a] * s[a];
LL x2 = - s[b], y2 = g[b] - s[b] * s[b];
if(x1 == x2) return -1e18;
return (y2 - y1) / (double) (x2 - x1);
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++) {
scanf("%lld", s + i);
s[i] += s[i - 1];
}
static int q[N], hd, bk;
for(int t = 1; t <= k; t ++) {
for(int i = 1; i <= n; i ++) g[i] = f[i];
hd = bk = 0;
for(int i = 1; i <= n; i ++) {
for(; bk - hd >= 2 && slope(q[hd], q[hd + 1]) <= s[i]; hd ++) ;
f[i] = 0;
if(hd < bk) {
int & j = q[hd]; fa[t][i] = j;
f[i] = g[j] + s[j] * (s[i] - s[j]);
}
for(; bk - hd >= 2 && slope(q[bk - 1], q[bk - 2]) >= slope(i, q[bk - 1]); bk --) ;
q[bk ++] = i;
}
}
printf("%lld\n", f[n]);
for(int x = fa[k][n]; k; x = fa[-- k][x])
printf("%d ", x);
return 0;
}
```
> upd: 感谢@chennengkuan 指出定义的小错误