SP33017 ADAMOLD - Ada and Mold 题解

# Description

Luogu传送门

vjudge传送门

不得不说，洛谷的翻译是真的迷，这里再给出一个翻译：

给你一个长度为 $n$ 的数列，让你把这个数列划分成 $k + 1$ 段。

定义一段区间的价值为区间内数字两两异或的和，即 $\sum\limits_{i = l}^r\sum\limits_{j = i + 1}^r(a_i \oplus a_j)$。

求一种划分方案使得 $k + 1$ 段价值和最小，只需要输出价值和。

数据范围：$1 \leq k < n \leq 5000, 0 \leq a_i \leq 10^9$

# Solution

首先考虑朴素的 $dp$，定义 $dp_{i, j}$ 表示前 $i$ 个数，划分成 $j$ 段的最小价值。

转移方程：

$$dp_{i, j} = \min\{dp_{k, j - 1} + w(k + 1, i)\}$$

也就是前 $k$ 个数划分成 $j - 1$ 段，$k + 1 \sim i$ 放到一段里，这一段的价值就是 $w(k + 1, i)$。

$w(i, j)$ 可以 $O(n^2)$ 预处理出来，然后转移也是 $O(n^3)$ 的，总复杂度 $O(n^3)$， 无法通过此题。

重点来了，我们要使用四边形不等式优化 dp。

关于四边形不等式优化 dp 的详细讲解请大家左转百度一下吧 QwQ

我们知道，四边形不等式需要满足如下条件：

$$w(a, c) + w(b, d) \leq w(a, d) + w(b, c)\ \ (a \leq b \leq c \leq d)$$

同时，我们知道只需要证明 $w(i, j) + w(i + 1, j + 1) \leq w(i, j + 1) + w(i + 1, j)$ 即可证明上述条件。

所以我们来推导一下：

$$\begin{aligned} & w(i, j + 1) + w(i + 1, j) - w(i, j) - w(i + 1, j + 1) \\ =& (w(i, j + 1) - w(i, j)) + (w(i + 1, j + 1) - w(i + 1, j)) \\ =& \sum_{t = i}^j (a_{j + 1} \oplus a_t) - \sum_{t = i + 1}^j (a_{j + 1} \oplus a_t) \\ \geq& 0 \end{aligned}$$

所以我们的转移方程满足四边形不等式。那么这个性质有什么用呢？

众所周知，拥有了这个性质之后我们就有了决策单调性，也就是 $p_{i, j - 1} \leq k \leq p_{i + 1, j}$。

$p_{i, j}$ 是转移到 $dp_{i, j}$ 时的最优决策点，就是上面转移方程里使得 $dp_{i, j}$ 取最优值时转移过来的那个 $k$。

所以我们在对 $dp_{i, j}$ 进行转移时只需要枚举 $p_{i, j - 1} \sim p_{i + 1, j}$ 即可。

# Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 5010;
const ll INF = 1e18;
int n, m;
int a[N], p[N][N];
ll f[N][N], s[N][N];

inline ll sum(int x, int y){
    return s[y][y] - s[x - 1][y] - s[y][x - 1] + s[x - 1][x - 1];
}

int main(){
    scanf("%d%d", &n, &m); m++;
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            s[i][j] = (a[i] ^ a[j]) + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j) f[i][j] = INF;
    f[0][0] = 0;
    for(int j = 1; j <= m; ++j){
        p[n + 1][j] = n;
        for(int i = n; i >= 1; --i)
            for(int k = p[i][j - 1]; k <= p[i + 1][j]; ++k)
                if(f[i][j] > f[k][j - 1] + sum(k + 1, i))
                    f[i][j] = f[k][j - 1] + sum(k + 1, i), p[i][j] = k;
    }
    printf("%lld\n", f[n][m] >> 1);
    return 0;
}

$$\_EOF\_$$