洛谷P3694 邦邦的大合唱站队

十一月 13, 2020 3328

题目描述

N个偶像排成一列，他们来自M个不同的乐队。每个团队至少有一个偶像。

现在要求重新安排队列，使来自同一乐队的偶像连续的站在一起。重新安排的办法是，让若干偶像出列（剩下的偶像不动），然后让出列的偶像一个个归队到原来的空位，归队的位置任意。

请问最少让多少偶像出列？

N \leq 10^5, M \leq 20

解题思路

看到 M \leq 20 自然想到状压。

考虑设 \texttt{stat} 的第 i 位表示第 i 个团队是(1)否(0)已经安排在一块了，并设 \texttt{f[stat]} 表示将 \texttt{stat} 中所有团队安排在队伍最前面的最小出列数。

比如 \texttt{stat} = 0110 ，就表示把第 2、3 个团队安排在队伍最前面，一种可能的分配方案是 [3333][222]14141441，也就是前面一连串全是 2、3 团队的人。

转移：
每次枚举一个 i \in \texttt{stat} 表示将要把第 i 个团队安排到所有 \texttt{stat} 里面的团队的最末尾，很容易就能确定这个团队要占据的位置为 [S(\texttt{stat}) - \mathrm{Size}(i), S(\texttt{stat})] ，其中 S 表示状态中所有团队大小的总和， \mathrm{Size} 表示某一个团队的大小。

1
2
3
4
5
比如 stat = 01110，当前枚举了第 2 个队伍要在最末尾
一种合法的分配方案是：
33344442221515115
其中 2 的左边界 7 正好是 S(01110) - Siz(2) = 10 - 3 = 7
2 的右边界 10 正好是 S(01110) = 10

显然，只需要让不属于团队 i 的人都出列即可。

所以转移方程是：

\texttt{f[stat]} = \min\{\texttt{f[stat\^ i] + People not in team i in }[l, r] \}

其中 l, r 为上面提到的边界，加号后面这个东西可以通过预处理前缀和来快速求。

时间复杂度 \mathcal{O}(m\times 2^m)

代码实现

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 
#define ALL(x) (x).begin(), (x).end()

#define count(x) (sum[n][(x)])

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e5 + 10;
const int MAXM = 20 + 5;
const int _M = 20 + 1;

int n, m;
int aa[MAXN];
int sum[MAXN][MAXM], sumbit[(1 << _M)];
int dp[(1 << _M)];

int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; ++i) {
        aa[i] = read();
        for (int j = 1; j <= m; ++j) {
            sum[i][j] += sum[i - 1][j];
        } sum[i][aa[i]] += 1;
    } 
    
    memset(dp, 0x3f, sizeof dp); dp[0] = 0;
    for (int stat = 1; stat <= (1 << m) - 1; ++stat) {
        int sumofchosen = 0;
        for (int i = 1; i <= m; ++i) if (stat & (1 << (i - 1))) sumofchosen += count(i);
        for (int i = 1; i <= m; ++i) {
            if (stat & (1 << (i - 1))) {
                int r = sumofchosen, l = (sumofchosen - count(i) + 1);
                dp[stat] = std::min(dp[stat], 
                    dp[stat ^ (1 << (i - 1))] + count(i) - (sum[r][i] - sum[l - 1][i]));
            }
        }
    } printf("%d\n", dp[(1 << m) - 1]);
    return 0;
}