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 }