CodeForces 1215E Marbles 题解

Description

给出一个长度为 n 的数列，$2\leq n\leq 4\ast 10^5$，每个数字 $a_i$ 都在 $[1,20]$ 内。
可以对这个数列中相邻的两个数字交换位置，最终要使得相同的数字都在一起。
求最小交换次数。

Link

Tags

状压DP

Analysis

$a_i \in [1,20]$，很明显可以用状压 DP。

首先可以发现一个重要的性质：如果交换相邻的两数，其他所有数字的相对位置是不变的。根据这个性质，在交换的时候我们就可以分开考虑每一种数字。
数字只有 20 种，则我们可以一种数字一种数字考虑，设 $F(mask)$ 为状态为 $mask$ 的最小交换位置。$mask$ 对应位上的 0 或 1 分别表示某种数字是否已经考虑。
接下来考虑状态转移，设现在状态已经是 $mask$，需要新增的数字是 $j$（$mask$ 中对应位为 0）。则我们可以直接把所有 $j$ 移动到最左边（如果最优解中此时 $j$ 不在最左边怎么办？则其他状态会涵盖这个方案）。
为了快速做到这一点，预处理一个数组 $cnt(i,j)$ 表示把所有 $i$ 数字移动到所有 $j$ 数字左边的最小交换次数。因为累加时交换彼此独立，预处理时可以看成一个队列里只有 $i$ 和 $j$ 两种数字，那么每个 i 需要的交换次数就是这个 i 之前 j 的个数。
则转移方程是：

$F(mask+2^j)=F(mask)+\sum_{k\in mask} cnt(j,k)$

实际上时间是 $\Theta (2^{20} \ast 20\ast 20)$，估算最多到 $4\ast 10^8$ 的亚子，还好时限是 4s……

Code

#include<bits/stdc++.h>
using namespace std;

#define int long long

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

const int maxn=400005,maxc=22;
const int maxs=1048576+10;
const int INF=0x3f3f3f3f3f3f3f3f;

int n,c=20,s=1<<20;
int a[maxn];
int cnt[maxc][maxc];
int f[maxs];
vector<int> vec[maxc];

signed main(){
    n=read();
    for (int i=1;i<=n;i++) a[i]=read()-1,vec[a[i]].push_back(i);

    for (int i=0;i<c;i++) if (vec[i].size())
        for (int j=0;j<c;j++) if (vec[j].size() && i!=j){
            int t=0;
            for (int k=0;k<vec[i].size();k++){
                while ((vec[j][t]<vec[i][k]) && (t+1<vec[j].size())) t++;
                cnt[i][j]+=t+(vec[j][t]<vec[i][k]);
            }
        }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for (int i=0;i<s;i++) if (f[i]!=INF){
        for (int j=0;j<c;j++) if ((i&(1<<j))==0){
            int nxt=i|(1<<j);
            int sum=0;
            for (int k=0;k<c;k++) if (i&(1<<k)) sum+=cnt[j][k];
            f[nxt]=min(f[nxt],f[i]+sum);
        }
    }
    printf("%lldn",f[s-1]);
    return 0;
}

好像很长时间没写正经博客了来着……