题目
给一段长度为$n$的序列，包含$1\sim m$的数字，可以任意交换两个数字的位置，目标是让所有相同的数字相邻，问最多可以有几个数字的位置不被交换。
题解
参照出题人的PPT。
把“已经排列好的数字种类的集合”视为状态，不考虑集合中数字的顺序，他们的总数是固定的，记状态为$s$，已经排列的人数为$f[s]$，这个可以在输入的时候直接求出来。$m$最大只有20，直接位运算来实现集合。$dp[s]$表示状态$s$最多能固定的数字数量。
枚举$s$，在每次枚举的时候枚举数字$i$，考虑
- $i$不在$s$中，则$dp[s|(1<<i)]=\max{dp[s]+sum[r][i]-sum[l-1][i]|i\in[0,m-1]}$
- $i$在$s$中，则$dp[s]=\max{dp[s\oplus(1<<i)]+sum[r][i]-sum[l-1][i]|i\in[0,m-1]}$
注意我为了方便位运算将输入序列全部减去1。
最后输出$dp[(1<<m)-1]$即可。
代码
因为一发入魂，所以没有写测试例生成和暴力验证。
AC代码
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>
#define DISPLAY_A 0
using namespace std;
const int MAX = 1e5 + 7;
unsigned int s;
int n, m;
int dp[1 << 21];
int f[1 << 21];
int a[MAX + 1];
int sum[MAX + 1][20 + 1];
int getSum(int c) {
int k = 0;
int ans = 0;
for (; c; c >>= 1, k++) {
ans += c & 1 ? sum[n][k] : 0;
}
return ans;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] -= 1;
for (int j = 0; j < m; j++) {
sum[i][j] = sum[i - 1][j] + (j == a[i]);
}
}
const int full = (1 << m) - 1;
for (int i = 0; i <= full; i++) {
f[i] = getSum(i);
}
while (s <= full) {
for (int i = 0; i < m; i++) {
int l = f[s] + 1;
int r = f[s | (1 << i)];
if (s & (1 << i)) {
dp[s] = max(dp[s], dp[s - (1 << i)] + sum[r][i] - sum[l - 1][i]);
} else {
dp[s | (1 << i)] = max(dp[s | (1 << i)], dp[s] + sum[r][i] - sum[l - 1][i]);
}
}
s++;
}
cout << dp[full] << endl;
return 0;
}
|