前言
题目链接：Codeforces；洛谷。
题意简述
给定长度为 \(n\) 的序列 \(a\)，你可以交换相邻元素，请问最少交换多少次使得序列连续，即对于每种颜色，其在序列中出现的位置都是连续一段。
\(m = \max \{ a_i \} \leq 20\)，\(n \leq 4 \times 10 ^ 5\)。
题目分析
对于“连续的序列”，不放看做我们给每种颜色钦定了一个优先级，然后按照优先级排了一个序。想到一个定理，将一个序列排序最少交换相邻元素的次数等于该序列的逆序对数。证明很简单，考虑冒泡排序的过程，我们每次交换相邻的逆序对，能够减少一对逆序对，而逆序对为 \(0\) 的时候，序列有序。由于每次操作做多使逆序对减少 \(1\)，所以操作次数至少是逆序对个数，而我们有证明了按照冒泡排序的方式，一定存在一种方式达到这个下限，所以得证。
看到数据范围，很容易想到状压 DP。记 \(f_{S}\) 表示只考虑集合 \(S\) 中的颜色，使得其连续的最小交换次数。最后答案就是 \(f_{\{i\}_{i = 1}^m}\)。边界 \(f_{\varnothing} = 0\)。
考虑由 \(f_{S \setminus \{ x \}}\) 转移到 \(f_{S}\)。此时 \(x\) 为 \(S\) 中我们钦定优先级最大的颜色，即我们需要让所有颜色为 \(x\) 的数交换到 \(S \setminus \{x \}\) 的右边。对于每一个 \(a_i = x\) 的 \(i\)，交换它的次数等于它的逆序对数，即有多少个 \(a_j \in S \setminus \{ x \} \land j > i\)。这个预处理 \(w_{u, v}\) 表示为了让颜色 \(u\) 全部到 \(v\) 的右边的交换次数即可。那么转移即为 \(f_{S} = \min \Big \{ f_{S \setminus \{x\}} + \sum \limits _{y\in S \setminus \{x\}} w_{x, y} \Big\}\)。
时间复杂度 \(\Theta(m 3^m + nm)\)，可以预处理优化掉转移的 \(\sum\)，时间复杂度：\(\Theta(m 2^m + 3^m + nm)\)。
代码
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 400010;
const int K = 20;
int n, k = 20, val[N];
int cnt[K], p[1 << K];
long long yzh[K][1 << K], dp[1 << K];
inline int lowbit(int x) {
return x & -x;
}
signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &val[i]), --val[i];
++cnt[val[i]];
for (int j = 0; j < k; ++j)
yzh[j][1 << val[i]] += cnt[j];
}
for (int i = 0; i < k; ++i) {
p[1 << i] = i;
for (int st = 1; st < 1 << k; ++st)
yzh[i][st] = yzh[i][st ^ lowbit(st)] + yzh[i][lowbit(st)];
}
for (int st = 1; st < 1 << k; ++st) {
dp[st] = 0x3f3f3f3f3f3f3f3f;
for (int S = st; S; S &= S - 1) {
int i = lowbit(S);
dp[st] = min(dp[st], dp[st ^ i] + yzh[p[i]][st ^ i]);
}
}
printf("%lld", dp[(1 << k) - 1]);
return 0;
}