洛谷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;
}
参考文献: