CodeForces 1215E Marbles 题解

/ 0评 / 0

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,需要新增的数字是 jmask 中对应位为 0)。则我们可以直接把所有 j 移动到最左边(如果最优解中此时 j 不在最左边怎么办?则其他状态会涵盖这个方案)。
为了快速做到这一点,预处理一个数组 cnt(i,j) 表示把所有 i 数字移动到所有 j 数字左边的最小交换次数。因为累加时交换彼此独立,预处理时可以看成一个队列里只有 ij 两种数字,那么每个 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;
}

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


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/cf1215e/


发表评论

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