题目描述

洛谷 P3694 邦邦的大合唱站队 状压DP-LMLPHP

输入输出样例

输入 #1 复制

输出 #1 复制

说明/提示

洛谷 P3694 邦邦的大合唱站队 状压DP-LMLPHP

分析

首先要注意合唱队排好队之后不一定是按\(1.2.3......m\)的顺序的

\(N\)的范围很大,但\(m\)的数据比较小,所以我们考虑装压DP

我们设\(f[i]\)为状态为\(i\)的合唱队已经安排好位置的最小花费

接下来就是状态转移方程的问题

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))) f[i]=min(f[i],f[i^(1<<(j-1))]+num[j]-sum[len][j]+sum[len-num[j]][j]);
}
}

第一维枚举的是状态,在枚举状态之后,我们还要统计当前状态下哪些合唱队已经排好了位置

我们用一个变量\(len\)记录排好队的总人数,如果当前合唱队已经排好了队,那么我们把总人数加上当前合唱队的人数

其中,编号为\(j\)的合唱队的总人数\(num[j]\)可以预处理

为什么这样做呢?

因为我们无论让偶像们怎么出队,他们最终的状态是确定的,肯定是一个合唱队的偶像站到一起,因此我们就可以统计排好队后当前区间的总长度

接下来就是状态转移

如果编号为\(j\)的合唱队在我们决策的范围之内,那我们就需要尝试将编号为\(j\)的合唱队的全体成员都放在队伍最后

那么此时我们就需要将编号为\(j\)的合唱队中不在区间\([len-num[j]+1,num[j]]\)的偶像移到该区间

此时的花费为\(num[j]-sum[len][j]+sum[len-num[j]][j]\)

其中\(sum[i][j]\)表示开始时前\(i\)个位置中编号为\(j\)的合唱队员的个数

问题就可以解决了

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=22,maxm=1e5+5;
int f[1<<maxn];
int num[maxn],sum[maxm][maxn];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int aa;
scanf("%d",&aa);
num[aa]++;
for(int j=1;j<=m;j++) sum[i][j]=sum[i-1][j];
sum[i][aa]++;
}
memset(f,0x3f,sizeof(f));
f[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))) f[i]=min(f[i],f[i^(1<<(j-1))]+num[j]-sum[len][j]+sum[len-num[j]][j]);
}
}
printf("%d\n",f[(1<< m)-1]);
return 0;
}
05-11 22:28