#状压DP# [luogu P3694] 邦邦的大合唱站队TitleSolutionRemarksCode(AC)

77 阅读 0 评论 51 点赞

我是靠谱客的博主幸福自行车，最近开发中收集的这篇文章主要介绍#状压DP# [luogu P3694] 邦邦的大合唱站队TitleSolutionRemarksCode(AC)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

`Title`

P3694 邦邦的大合唱站队

`Solution`

注意：三目运算符千万记得加括号，否则会出锅，优先级很低
设 $f [i]$ 表示在 $i$ 状态（从左到右处理完了那些乐队）下出队人数最少的数量。
$a [i] [j]$ 记录的是前缀和。
每次更新 $f [i] = m i n (f [i], f [i x o r (1 < < (j - 1))] + n u m [j] - a [t o t] [j] + a [t o t - n u m [j]] [j])$

`Remarks`

暴力程序（计次优化）

#include<cstdio>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std; 
const int N=1e5+5; 
int n,m,a[N],ans=N,b[N],c[25]; bool d[N],cc=0; 	
long long yy=0; 
int check(int y){
	int q=0,w=0; 
	rep(i,1,y) {
		rep(j,1,c[b[i]]) 
			if (a[++q]!=b[i]) w++; 		
	}
	return w; 	
}
void dfs(int x){
	if (!cc){
		yy++; 
		if (yy>1e3) {
			cc=1; 
			return; 
		}
	} else return; 
	if (check(x-1)>=ans) return;	
	if (x>m){
		ans=min(ans,check(m));
		return; 
	}
	rep(i,1,m) if (!d[i]&&!cc) {
		d[i]=1; b[x]=i; 
		dfs(x+1); 
		d[i]=0; b[x]=0; 
	}
}
int main(){
	scanf("%d%d",&n,&m); 
	rep(i,1,n) scanf("%d",&a[i]),c[a[i]]++; 
	dfs(1); 
	printf("%d",ans); 
	return 0; 
}

`Code(AC)`

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std; 
const int N=1e5+5; 
const int M=21; 
int n,m; 
int read(){
	int p=0; char c=getchar(); 
	while (!isdigit(c)) c=getchar(); 
	while (isdigit(c)) p=(p<<3)+(p<<1)+c-48,c=getchar(); 
	return p; 
}
int a[N][M],f[(1<<M)],q,w,b[M]; 
int main(){
	n=read(),m=read(); 
	int ms=1<<m; 
	rep(i,1,n){
		b[(q=read())]++; 
		rep(j,1,m) a[i][j]=a[i-1][j]+((q==j)?1:0);
	}
	memset(f,0x3f,sizeof(f)); f[0]=0; 
	rep(i,1,ms-1){
		q=0; 
		rep(j,1,m) if (i&(1<<(j-1))) q+=b[j];
		rep(j,1,m) if (i&(1<<(j-1))) 
			f[i]=min(f[i],f[i^(1<<(j-1))]+b[j]-a[q][j]+a[q-b[j]][j]); 
	}
	printf("%d",f[ms-1]); 
	return 0; 
}