题目背景
BanG Dream!里的所有偶像乐队要一起大合唱，不过在排队上出了一些问题。
题目描述
N个偶像排成一列，他们来自M个不同的乐队。每个团队至少有一个偶像。
现在要求重新安排队列，使来自同一乐队的偶像连续的站在一起。重新安排的办法是，让若干偶像出列（剩下的偶像不动），然后让出列的偶像一个个归队到原来的空位，归队的位置任意。
请问最少让多少偶像出列？
输入输出格式
输入格式： 第一行2个整数N，M。
接下来N个行，每行一个整数，表示队列中第i个偶像的团队编号。
输出格式： 一个整数，表示答案
输入输出样例
输入样例#1： 12 4 1 3 2 4 2 1 2 3 1 1 3 4 输出样例#1： 7 说明
【样例解释】
1 3 √ 3 3 2 3 √ 4 4 2 4 √ 1 2 √ 2 2 3 2 √ 1 1 1 1 3 1 √ 4 1 √ 【数据规模】
对于20%的数据，
对于40%的数据，
对于70%的数据，
对于全部数据，
题解 暴力：枚举答案的排列状态，判断有多少位置是不一样的，取最小值即可。 正解：我们发现M只有20，想到状压，我们不妨从队列一端往另一端DP，记f[i]表示i状态下最小的交换次数（比如f[1001]表示队列左端都为1,4偶像切符合要求的最小交换次数），转移就枚举从哪种偶像转移过来就行了。详见代码。
代码
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #define inf 10000000 int sum[100005][25],f[1050000],num[25],c[25],a[100005]; int n,m; using namespace std; void init()//比赛时快速读入只有20分（TLE），不用数组读入70分（WA），无语了。。。 { scanf("%d",&n);scanf("%d",&m); for (int i=1;i<=m;i++) c[i]=1<<(i-1); for(int i=1;i<=n;i++)scanf("%d",a+i); for(int i=1;i<=n;i++) { num[a[i]]++; for(int j=1;j<=m;j++) { sum[i][j]=sum[i-1][j]+(a[i]==j); } } } int asklen(int x) { int ans=0; for (int i=1;i<=m;i++) { if (x&c[i]) ans+=num[i]; } return ans; } int main() { init(); int N=(1<<m)-1; for (int i=1;i<=N;i++) { f[i]=inf; int len=asklen(i); for (int j=1;j<=m;j++) { if (i&c[j]) { f[i]=min(f[i],f[i^c[j]]+num[j]-(sum[len][j]-sum[len-num[j]][j])); } } } printf("%d",f[N]); return 0; }