洛谷P3694 邦邦的大合唱
2024-09-06 10:44:16
题目背景
BanG Dream!里的所有偶像乐队要一起大合唱,不过在排队上出了一些问题。
题目描述
N个偶像排成一列,他们来自M个不同的乐队。每个团队至少有一个偶像。
现在要求重新安排队列,使来自同一乐队的偶像连续的站在一起。重新安排的办法是,让若干偶像出列(剩下的偶像不动),然后让出列的偶像一个个归队到原来的空位,归队的位置任意。
请问最少让多少偶像出列?
输入输出格式
输入格式:
第一行2个整数N,M。
接下来N个行,每行一个整数a_i(1\le a_i \le M)ai(1≤ai≤M),表示队列中第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%的数据,N≤20,M=2
对于40%的数据,N≤100,M≤4
对于70%的数据,N≤2000,M≤10
对于全部数据,1≤N≤105,M≤20
这竟然是一道签到题,我觉得自己可以滚回普及组了。
反过来考虑,要让最少的人出列就是让最多的人不出列(留下)。
看m数据范围就是状压dp。然后n。。发现n挺大的,如果能让最后主算法复杂度不带n是最好的,反正复杂度不能让n和(1<<m)相乘
我们预处理出tot[i][j]表示前i个人中,团队序号为j的人有多少个,复杂度O(nm)。
然后枚举每个状态,看看这个状态可以转移到那些状态。
用dp[i]表示第i个状态(如果 j 满足 (1<<(j-1)) & i != 0,则表示j这个团队的人全都排好了,而且位置在靠前的位置)可以留下的最多人数,然后就可以dp了。
for(int i=0;i<(1<<m);++i) {
sum=0;
for(int j=1;j<=m;++j) if(i&(1<<(j-1))) sum+=tot[n][j];
l=sum;
for(int j=1;j<=m;++j) {
if(i&(1<<(j-1))) continue;
r=sum+tot[n][j];
dp[i|(1<<(j-1))]=max(dp[i|(1<<(j-1))],dp[i]+tot[r][j]-tot[l][j]);
}
ans=max(ans,dp[i]);
}
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e5+10,maxm=20,maxmi=1<<20;
int n,m,a[maxn],tot[maxn][maxm],dp[maxmi],ans; int aa;char cc;
int read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
} int main() {
n=read();m=read();
for(int i=1;i<=n;++i) {
a[i]=read();
for(int j=1;j<=m;++j) tot[i][j]=tot[i-1][j];
tot[i][a[i]]++;
}
int sum,l,r;
for(int i=0;i<(1<<m);++i) {
sum=0;
for(int j=1;j<=m;++j) if(i&(1<<(j-1))) sum+=tot[n][j];
l=sum;
for(int j=1;j<=m;++j) {
if(i&(1<<(j-1))) continue;
r=sum+tot[n][j];
dp[i|(1<<(j-1))]=max(dp[i|(1<<(j-1))],dp[i]+tot[r][j]-tot[l][j]);
}
ans=max(ans,dp[i]);
}
printf("%d",n-ans);
return 0;
}
最新文章
- 【C#】分享带等待窗体的任务执行器一枚
- ADO.NET 中的新增功能
- SpringMVC框架介绍
- [ERROR] Failed to execute goal org.apache.maven.plugins:maven-archetype-plugin:2.4:create (default-cli) on project standalone-pom: Unable to parse configuration of 3: mojo org.apache.maven.plugins:
- idea 新建web项目
- JAVA https证书相关
- 【web】 亿级Web系统搭建——单机到分布式集群
- Linux C 程序 预处理,结构体(13)
- cocos2dx内存管理的一些看法
- redhat7.3配置163 yum源
- (简单) POJ 3076 Sudoku , DLX+精确覆盖。
- Session保存到指定数据库中
- tomcat 绑定ipv4端口
- jetty切换tomcat中文乱码
- LINUX负载均衡LVS-DR搭建
- Thumbnailator java图片压缩,加水印,批量生成缩略图
- nuget.org 无法加载源 https://api.nuget.org/v3/index.json 的服务索引
- jquery,禁止冒泡和默认行为
- Dubbo实践(七)扩展点
- Spring中通配符(转)