Luogup3694 Bangbang chorus standing in line

Background

BanG Dream! All the idols in the band are going to sing together , But there were some problems in the queue .

Title Description

N A line of idols , They come from M A different band . Each team has at least one idol .

Now it's required to reschedule , Make the idols from the same band stand together continuously . The way to rearrange is , Let some idols stand out （ The rest of the idols don't move ）, Then let the idols return one by one to the original empty seats , Return to any position .

At least how many idols are allowed to be listed ？

Input format

first line 2 It's an integer N,M.

Next N Row , One integer per row $a_i(1\le a_i\le M)$, Represents the second in the queue i An idol's team number .

Output format

An integer , Answer

Examples #1

The sample input #1

12 4
1
3
2
4
2
1
2
3
1
1
3
4

Sample output #1

7

Tips

【 Sample explanation 】

1  3   √
3  3
2  3   √
4  4
2  4   √
1  2   √
2  2
3  2   √
1  1
1  1
3  1   √
4  1   √

【 Data scale 】

about 20% The data of ,$N\le 20,M=2$

about 40% The data of ,$N\le 100,M\le 4$

about 70% The data of ,$N\le 2000,M\le 10$

For all data ,$1\le N\le 10^5,M\le 20$

analysis

For the total number of bands, only 20, Consider the pressure DP

dp Array setting ：

Set the State $S$ Represents a collection of currently scheduled teams

Such as $011$ It's already arranged $1,2$ Team

$dp[s]$ To arrange the minimum number of people out of these teams

Arrange the people of these teams , That is to convert the team into

$11111222223333....44444758666859595$（ Suppose there is 9 A team

here $S$ by 1111, The team $1,2,3,4$ All the people are lined up

Transfer ：

Arrange well $x$ The length of the teams is this $x$ The sum of the number of teams $len$

So we need to count the number of people in each team $num[i]$( The team i The total number of people )

Suppose we are currently putting the $j$ A team of people are arranged behind the team （ Is in the $S$ State, $j$ The people in the team are behind the arranged team ）

that $j$ The position of the team is $num[j]$ individual

therefore $j$ The team will stand $[len-num[j],len]$ The location of

set up $sum[i][j]$ To the current location $i$ It's about $j$ There are several people in the team ( The prefix and )

So transfer to ：

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

PS: Draw a picture ： Grey is the range of value

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-mUBQBH10-1655909895836)(file://C:\Users\Administrator\AppData\Roaming\marktext\images\2022-06-22-22-56-37-image.png?msec=1655909797525)]

Why $ xor $ Well ?

$ixor(1<<(j-1))$ Is equivalent to $i$ The second under binary $j-1$ The assignment is 0, Express $j$ The state before the team is not ranked

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;
}