luoguP3694邦邦的大合唱站队

题目背景

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

题目描述

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

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

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

输入格式

第一行2个整数N，M。

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

输出格式

一个整数，表示答案

样例 #1

样例输入 #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%的数据，$N\le 20,M=2$

对于40%的数据，$N\le 100,M\le 4$

对于70%的数据，$N\le 2000,M\le 10$

对于全部数据，$1\le N\le 10^5,M\le 20$

分析

对于乐队总数只有20，考虑状压DP

dp数组的设定：

设状态$S$表示为当前已经排好的团队的集合

如$011$为已经排好了$1，2$号团队

$dp[s]$为排列这些团队最小出队人数

排列好这些团队的人，即为把队伍转换为

$11111222223333....44444758666859595$（假设有9个团队

此时$S$为1111,即团队$1,2,3,4$的人都排列好了

转移：

排列好$x$个团队排列的长度为这$x$个团队的人数之和$len$

所以我们需要统计每个团队的人数$num[i]$(团队i的总人数)

假设我们当前正在将第$j$个团队的人安排到队伍后面（就是在$S$状态下$j$团队的人位于排列好团队的后边）

那么$j$团队的人站的位置为$num[j]$ 个

所以 $j$团队的人将站在$[len-num[j],len]$的位置

设$sum[i][j]$为到当前位置$i$处$j$团队的人出现了几个(前缀和)

那么转移为：

$dp[i]=min(dp[i],dp[ixor(1<<(j-))]+num[j]-sum[len][j]+sum[len-num[j]][j]$

PS:画个图：灰色为产生价值的区间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mUBQBH10-1655909895836)(file://C:\Users\Administrator\AppData\Roaming\marktext\images\2022-06-22-22-56-37-image.png?msec=1655909797525)]

为什么是$ xor $呢?

$ixor(1<<(j-1))$相当于将$i$二进制下的第$j-1$赋值为0，表示$j$团队没有被排列前的状态

CODE

#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int n,m;
int dp[1<<22];
int num[maxn];
int sum[maxn][22]; 
int main(){
    
	scanf("%d%d",&n,&m);
	for(int x,i=1;i<=n;i++){
    
		scanf("%d",&x);
		num[x]++;
		for(int j=1;j<=m;j++)sum[i][j]=sum[i-1][j];
		sum[i][x]++;
	}	
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<(1<<m);i++){
    
		int len=0;
		for(int j=1;j<=m;j++){
    
			if(i&(1<<(j-1)))len+=num[j];
		} 
		for(int j=1;j<=m;j++){
    
			if(i&(1<<(j-1)))dp[i]=min(dp[i],dp[i^(1<<(j-1))]+num[j]-sum[len][j]+sum[len-num[j]][j]);
		}
	}
	cout<<dp[(1<<m)-1];
	return 0;
}