洛谷P3694 邦邦的大合唱站队 题解

题目链接：P3694 邦邦的大合唱站队

题意：

BanG Dream!里的所有偶像乐队要一起大合唱，不过在排队上出了一些问题。

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

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

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

输入格式：

第一行 $2$ 个整数 $n,m$。

接下来 $n$ 行，每行一个整数 $a_i(1\le a_i \le m)$ ，表示队列中第 $i$ 个偶像的团队编号。

输出格式：

一个整数，表示答案。

数据范围：

$1\le n\le 10^5,~ m\le 20$

可以发现，我们并不关心换了哪些人，而在乎换了多少人。

例如一个段应当放满 $\mathtt{B}$ 的人，结果里面 $\mathtt{B : C : D} = \mathtt{3 : 2 : 3}$ ，那我们肯定是把剩下那五个换成后面的 $\mathtt{B}$ 人。

考虑设 $f_S$ 表示已经站好的乐队的集合为 $S$ 时的最小花费，则（记 $\operatorname{cnt}(i)$ 表示乐队 $i$ 的人数）

$$f_S \downarrow f_{S \setminus {\{i\}}} + \operatorname{cnt}(i) - (s_{r,i} - s_{l,i})$$

其中 $r = \sum_{j \in S} \operatorname{cnt}(j), ~l = \sum_{j \in S} \operatorname{cnt}(j) - \operatorname{cnt}(i),~s_{i,j}$ 表示初始状态下前 $i$ 个位子中编号为 $j$ 的乐队的人数

时间复杂度 $\mathcal{O}(m2^m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define M 25

int n,m,f[N * M],s[N][M],cnt[M],sz[N * M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1, x; i <= n; i++)
    {
        cin >> x;
        for(int j = 1; j <= m; j++) s[i][j] = s[i - 1][j];
        ++s[i][x]; ++cnt[x];
    }
    for(int i = 0; i < m; i++) sz[1 << i] = cnt[i + 1];
    for(int i = 1; i < (1 << m); i++) if(!sz[i])
        sz[i] = sz[i & (-i)] + sz[i ^ (i & (-i))];
    memset(f, 0x3f, sizeof(f)); f[0] = 0;
    for(int i = 1; i < (1 << m); i++)
        for(int j = 1; j <= m; j++) if(i & (1 << (j - 1)))
        {
            int l = sz[i ^ (1 << (j - 1))], r = sz[i];
            down(f[i], f[i ^ (1 << (j - 1))] + (r - l) - (s[r][j] - s[l][j]));
        }
    cout << f[(1 << m) - 1] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/XTZORZ/solution-p3694