当前位置:网站首页>luoguP3694邦邦的大合唱站队
luoguP3694邦邦的大合唱站队
2022-07-03 12:07:00 【Oops_Corsini】
题目背景
BanG Dream!里的所有偶像乐队要一起大合唱,不过在排队上出了一些问题。
题目描述
N个偶像排成一列,他们来自M个不同的乐队。每个团队至少有一个偶像。
现在要求重新安排队列,使来自同一乐队的偶像连续的站在一起。重新安排的办法是,让若干偶像出列(剩下的偶像不动),然后让出列的偶像一个个归队到原来的空位,归队的位置任意。
请问最少让多少偶像出列?
输入格式
第一行2个整数N,M。
接下来N个行,每行一个整数 a i ( 1 ≤ a i ≤ M ) a_i(1\le a_i \le M) ai(1≤ai≤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 ≤ 20 , M = 2 N\le 20, M=2 N≤20,M=2
对于40%的数据, N ≤ 100 , M ≤ 4 N\le 100, M\le 4 N≤100,M≤4
对于70%的数据, N ≤ 2000 , M ≤ 10 N\le 2000, M\le 10 N≤2000,M≤10
对于全部数据, 1 ≤ N ≤ 1 0 5 , M ≤ 20 1\le N\le 10^5, M\le 20 1≤N≤105,M≤20
分析
对于乐队总数只有20,考虑状压DP
dp数组的设定:
设状态 S S S表示为当前已经排好的团队的集合
如 011 011 011为已经排好了 1 , 2 1,2 1,2号团队
d p [ s ] dp[s] dp[s]为排列这些团队最小出队人数
排列好这些团队的人,即为把队伍转换为
11111222223333....44444758666859595 11111222223333....44444 758666859595 11111222223333....44444758666859595(假设有9个团队
此时 S S S为1111,即团队 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4的人都排列好了
转移:
排列好 x x x个团队排列的长度为这 x x x个团队的人数之和 l e n len len
所以我们需要统计每个团队的人数 n u m [ i ] num[i] num[i](团队i的总人数)
假设我们当前正在将第 j j j个团队的人安排到队伍后面(就是在 S S S状态下 j j j团队的人位于排列好团队的后边)
那么 j j j团队的人站的位置为 n u m [ j ] num[j] num[j] 个
所以 j j j团队的人将站在 [ l e n − n u m [ j ] , l e n ] [len-num[j],len] [len−num[j],len]的位置
设 s u m [ i ] [ j ] sum[i][j] sum[i][j]为到当前位置 i i i处 j j j团队的人出现了几个(前缀和)
那么转移为:
d p [ i ] = m i n ( d p [ i ] , d p [ i x o r ( 1 < < ( j − ) ) ] + n u m [ j ] − s u m [ l e n ] [ j ] + s u m [ l e n − n u m [ j ] ] [ j ] dp[i]=min(dp[i],dp[i xor (1<<(j-))]+num[j]-sum[len][j]+sum[len-num[j]][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 $呢?
i x o r ( 1 < < ( j − 1 ) ) ixor(1<<(j-1)) ixor(1<<(j−1))相当于将 i i i二进制下的第 j − 1 j-1 j−1赋值为0,表示 j j 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;
}
边栏推荐
- 公纵号发送提示信息(用户微服务--消息微服务)
- [comprehensive question] [Database Principle]
- [review questions of database principles]
- C graphical tutorial (Fourth Edition)_ Chapter 15 interface: interfacesamplep271
- Enter the length of three sides of the triangle through the user, and calculate the area of the triangle, where the length is a real number
- A large select drop-down box, village in Chaoyang District
- Node. Js: use of express + MySQL
- [exercice 7] [principe de la base de données]
- I'm too lazy to write more than one character
- 2021 autumn Information Security Experiment 1 (password and hiding technology)
猜你喜欢
Ali & ant self developed IDE
并网-低电压穿越与孤岛并存分析
电压环对 PFC 系统性能影响分析
Differences between initial, inherit, unset, revert and all
Public and private account sending prompt information (user microservice -- message microservice)
自抗扰控制器七-二阶 LADRC-PLL 结构设计
Sword finger offer05 Replace spaces
阿里大于发送短信(用户微服务--消息微服务)
记录自己vulnhub闯关记录
Four problems and isolation level of MySQL concurrency
随机推荐
alright alright alright
Alibaba is bigger than sending SMS (user microservice - message microservice)
Swift5.7 extend some to generic parameters
How to convert a decimal number to binary in swift
Four problems and isolation level of MySQL concurrency
The latest version of blind box mall thinkphp+uniapp
Airflow installation jump pit
Flinksql can directly create tables and read MySQL or Kafka data on the client side, but how can it automatically flow and calculate?
[review questions of database principles]
初入职场,如何快速脱颖而出?
Tianyi ty1208-z brush machine detailed tutorial (free to remove)
Social community forum app ultra-high appearance UI interface
4. Wireless in vivo nano network: electromagnetic propagation model and key points of sensor deployment
C graphical tutorial (Fourth Edition)_ Chapter 20 asynchronous programming: examples - cases without asynchronous
Enter the length of three sides of the triangle through the user, and calculate the area of the triangle, where the length is a real number
Sqoop1.4.4原生增量导入特性探秘
Sword finger offer14 the easiest way to cut rope
Gan totem column bridgeless boost PFC (single phase) seven PFC duty cycle feedforward
It feels great to know you learned something, isn‘t it?
Create a dojo progress bar programmatically: Dojo ProgressBar