これこそシュタインズ・ゲートの选択だ

CF1215E – Marbles

CF1215E – Marbles

题意:给定一个长度为n的序列,每次操作可以交换相邻连个数,求最少需要几次操作使得所有颜色都是连续的。

n\le 5*10^41\le a_i \le 20

思路:简单的状压dp,令g[i][j]表示将所有颜色为i的数操作到颜色为j的数之前所需的最小操作次数。

以上可以预处理,然后就没了

代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int s=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
	return s;
}
const int N=2e6+5;
typedef long long ll;
int n;
int a[N];ll f[N];
vector<int> col[20];
ll g[20][20];
inline void chkmin(ll &x,ll y){if(y<x) x=y;}
int main(){
	n=read();
	for(int i=1;i<=n;i++) {
		a[i]=read()-1;
		col[a[i]].push_back(i);
	}
	for(int i=0;i<20;i++)
		for(int j=0;j<20;j++){
			if(i==j||!col[i].size()||!col[j].size()) continue;
			int p=0;
			for(int u:col[i]){
				while(1) {
					if(p==col[j].size()-1||col[j][p+1]>u) break;
					p++;
				}
				if(u>col[j][p]) g[i][j]+=p+1;
			}
		}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int s=0;s<(1<<20);s++)
		for(int i=0;i<20;i++)
			if(!((s>>i)&1)){
				ll sum=0;
				for(int j=0;j<20;j++)
					if((s>>j)&1) sum+=g[j][i];
				chkmin(f[s|(1<<i)],f[s]+sum); 
			}
	cout<<f[(1<<20)-1];
	return 0;
}


发表评论

电子邮件地址不会被公开。 必填项已用*标注