https://codeforces.com/contest/1215/problem/E
cnt[x][j]表示把x这种颜色全放到j这种颜色前面所需要的交换次数。
其实这题跟上一篇博客那题是同一个套路，难点在于想到预处理出cnt数组来进行转移。
1 #define bug(x) cout<<#x<<" is "<<x<<endl
2 #define IO std::ios::sync_with_stdio(0)
3 #include <bits/stdc++.h>
4 #define iter ::iterator
5 //#define pa pair<int,int>
6 using namespace std;
7 #define ll long long
8 #define mk make_pair
9 #define pb push_back
10 #define se second
11 #define fi first
12 #define ls o<<1
13 #define rs o<<1|1
14 ll mod=998244353;
15 const int inf=2e9+10;
16 const int N=(1<<20)+5;
17 ll d[N],cnt[25][25],sum[25];
18 int n;
19 int main(){
20 IO;
21 cin>>n;
22 for(int i=1;i<=n;i++){
23 int x;
24 cin>>x;
25 x--;
26 for(int j=0;j<20;j++){
27 cnt[x][j]+=sum[j];
28 }
29 sum[x]++;
30 }
31 for(int i=0;i<=N-2;i++)d[i]=1e18;
32 d[0]=0;
33 for(int s=0;s<(1<<20);s++){
34 for(int i=0;i<20;i++){
35 if(!((s>>i)&1)){
36 ll res=0;
37 for(int j=0;j<20;j++){
38 if((s>>j)&1){
39 res+=cnt[i][j];
40 }
41 }
42 int ns=s^(1<<i);
43 d[ns]=min(d[ns],d[s]+res);
44 }
45 }
46 }
47 cout<<d[(1<<20)-1]<<endl;
48 }