【HYSBZ】【带权二分】【斜率优化】4518 征途

HYSBZ 4518 征途

◇题目传送门◆

题目大意

给定$N$个数的序列$A$，要求将这个序列划分成$M$个连续的段，求这$M$段的方差乘上$M^2$的值。

分析

设最终划分的$M$段的每段的总和为$x_i$。

先来推一发式子：$$\begin{array}{rl}{M}^2{S}^2& =M^2\times \frac{1}{M}\sum _{i=1}^M(x_i?\bar{x}{)}^2\\ & =M\times \sum _{i=1}^M({x_i}^2?2\bar{x}{x}_i+{\bar{x}}^2)\\ & =M\times (\sum _{i=1}^M{x_i}^2?2\bar{x}\sum _{i=1}^M{x}_i+M{\bar{x}}^2)\\ & =\sum _{i=1}^M{x_i}^2?{\left(\sum _{i=1}^M{x}_i\right)}^2\end{array}$$

不难发现后面的那个是定值，我们只需要最小化前面的那个就可以了。

然而恰好选出$M$段有点麻烦。而我们发现$M$越大，答案会变小。感性理解一下就是个下凸函数，所以我们可以考虑带权二分。

设$s$为$x$的前缀和。

我们将每一段的代价都加上一个值$v$，则状态转移方程就变为f(i)=min?j=1i{f(j)+(sj?si)2+v}f(i)=\min_{j=1}^{i}\{f(j)+(s_j-s_i)^2+v\}f(i)=minj=1i?{ f(j)+(sj??si?)2+v}。

看到这个转移方程我们不难发现可以进行斜率优化：

对于决策点$k,j$，若$k$优于$j$，即$f(k)+(s_i?s_k{)}^2\le f(j)+(s_i?s_j{)}^2$，那么拆掉平方项并移项，得到$$2s_i\ge \frac{f(k)?f(j)+{s_k}^2?{s_j}^2}{s_k?s_j}$$

发现这个斜率的横坐标是单调递增的，所以直接单调队列维护即可。

参考代码

#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;typedef long long ll;
const int Maxn = 3000;int N, M;
int A[Maxn + 5];
ll sum[Maxn + 5], f[Maxn + 5];
int g[Maxn + 5];inline double slope(int x, int y) {
    return 1.0 * (f[y] - f[x] + sum[y] * sum[y] - sum[x] * sum[x]) / (sum[y] - sum[x]);
}
bool check(ll val) {
    static int q[Maxn + 5], head, tail;q[head = tail = 0] = 0;for(int i = 1; i <= N; i++) {
    while(head < tail && slope(q[head], q[head + 1]) < 2 * sum[i])head++;int j = q[head];f[i] = f[j] + val + (sum[i] - sum[j]) * (sum[i] - sum[j]);g[i] = g[j] + 1;while(head < tail && slope(q[tail - 1], q[tail]) > slope(q[tail], i))tail--;q[++tail] = i;}return g[N] > M;
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d %d", &N, &M);for(int i = 1; i <= N; i++)scanf("%d", &A[i]);for(int i = 1; i <= N; i++)sum[i] = sum[i - 1] + A[i];ll lb = 0, ub = sum[N] * sum[N];ll ans = 0;while(lb <= ub) {
    int mid = (lb + ub) >> 1;if(check(mid)) lb = mid + 1;else ub = mid - 1, ans = M * (f[N] - mid * M) - sum[N] * sum[N];}printf("%lld\n", ans);return 0;
}