题解 P3694 【邦邦的大合唱站队】
yu__xuan
·
·
题解
题目
P3694 邦邦的大合唱站队
思路
状压 dp。因为乐队数 m \leq 20，考虑将现在排好了哪些乐队压为二进制。
如共 8 支乐队已经排好了1,3 和 4 号乐队那么对应的二进制数为 00001101。
$sum[i][j]$ 表示原来的顺序中前 $i$ 个人中有几个是 $j$ 号乐队的。
$f[i]$ 表示排好了 $i$ 这些乐队最少需要多少人出队。
动态转移方程如下：
```cpp
if (i & (1 << (j - 1))) {
int l = s[i ^ (1 << j - 1)], r = s[i];
f[i] = min(f[i], f[i ^ (1 << (j - 1))] + sum[n][j] - sum[r][j] + sum[l][j]);
}
```
含义为，已经排好了 $i$ 这些乐队，$j$ 是其中的一支考虑将 $j$ 放到已经排好的这些乐队的最后那么就可以用排好了 $i \oplus j$ 这些乐队的最优情况 $f[i \oplus (1 << (j - 1))]$ 以及不在 $[s[i \oplus (1 << (j - 1))] + 1, s[i]]$ 这个区间中的 $j$ 号乐队的人数 $sum[n][j] - sum[s[i]][j] + sum[s[i \oplus (1 << j - 1)]][j]$ 来更新 $f[i]$。
### Code
```cpp
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define inf 2147483647
#define MAXN (1 << 20) + 1
int n, m, sum[100001][21];
int s[MAXN], f[MAXN];
int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d %d", &n, &m);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
for (int j = 1; j <= m; ++j) {
sum[i][j] = sum[i - 1][j];
}
++sum[i][x];
}
for (int i = 0; i < (1 << m); ++i) {
int d = i, cnt = 0;
while(d) {
++cnt;
if(d & 1) s[i] += sum[n][cnt];
d >>= 1;
}
f[i] = inf;
}
f[0] = 0;
for (int i = 0; i < (1 << m); ++i) {
for (int j = 1; j <= m; ++j) {
if (i & (1 << (j - 1))) {
int l = s[i ^ (1 << j - 1)], r = s[i];
f[i] = min(f[i], f[i ^ (1 << (j - 1))] + sum[n][j] - sum[r][j] + sum[l][j]);
}
}
}
printf("%d\n", f[(1 << m) - 1]);
return 0;
}
```