codeforces#1215E. Marbles(状压DP)

题目大意：给出一个由N个整数组成的序列，通过每次交换相邻的两个数，使这个序列的每个相同的数都相邻。求最小的交换次数。

比如给出序列：1 2 3 2 1 ，那么最终序列应该是 1 1 2 2 3 ，最小交换次数为4.

可以发现这道题的操作比较复杂，N的数量级也很大，\(N^2\)的时间复杂度肯定是行不通的。

对于这种题，我们可以先通过几组样例来构思出整道题的模型。

所以我们不妨考虑只有两种数的情况，对于数列 \(11221\)，它的最终状态其实有两种\(11122\)和\(22111\)。我们统计每个数字2前面与它不同的数字的个数，分别是 2 + 2共需4次，这就是将所有的数字2全部移到左边所需要的次数，同理统计1的话只需2次。

现在我们来考虑多种数字的情况。我们发现这种情况不能直接通过上述方法来得出。但可以得到一个普遍的但不一定是最优的方法：

每次将一种数字全部移到左边，再将第二种数字全部移到左边（这时我们不能考虑第一种数字）。。。依次类推。

但每次移动哪种数字我们却不能确定，于是可以使用状压DP。

因为题目中\(1<=A_{i}<=20\)。设当前状态为S，如果S的第\(i\)位为1，则第\(i\)种颜色已经被选过，统计答案时便不需要统计第\(i\)种。

（大致思路已经给出，具体变量的含义请见注释）

#include <bits/stdc++.h>

using namespace std;

#define N 400010

#define M 30

#define LL long long

int A[N],n,pre[M][M];

LL f[1<<21];

vector<int> chos[M];

int main() {

	cin>>n;

	for(LL i=1;i<=n;i++) {

		cin>>A[i];

		chos[A[i]].push_back(i);//统计每种数字的下标，放入vector储存

	}

	//预处理

	for(LL i=1;i<=20;i++)

		for(LL j=1;j<=20;j++) {

			if(i==j || chos[i].size()==0 || chos[j].size()==0) continue;

			//统计答案

			for(LL k=0,v;k<chos[i].size();k++) {

				v=chos[i][k];

				if(v<chos[j][0]) continue;

				pre[i][j]+=lower_bound(chos[j].begin(),chos[j].end(),v)-chos[j].begin();

				//二分查找离当前数字最近的指定的下标，这就是需要交换的次数，进行累加

			}

		}

	memset(f,0x3f,sizeof(f));

	f[0]=0;

	for(LL i=0;i<(1<<20);i++)

		for(LL j=1;j<=20;j++) //DP部分

			if(!(i&(1<<(j-1)))) {

				LL sum=0;

				for(LL k=0;k<20;k++)

					if(i&(1<<k))

						sum+=pre[k+1][j];

				f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+sum);

			}

	cout<<f[(1<<20)-1];

}