CF1215题解

E

假设从小到大排序，每次交换相邻两个，最小次数即冒泡排序也就是逆序对

考虑值域较小，把每个值映射到\([1,20]\)

设\(f_i\)为已经加入集合为\(i\)的值的最小逆序对个数，考虑填表法
即枚举每个在i里的数x，考虑其为最后加进来的数
再枚举其他的数y，考虑在原序列中形似(x,y)的个数，这个很容易预处理出来

#include<bits/stdc++.h>
typedef long long LL;
const LL maxn=1e6+9,inf=0x3f3f3f3f3f3f3f3f;
inline LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<3)+(x<<1)+c-'0'; c=getchar();
    }return x*f;
}
LL n;
LL a[maxn],cnt[29],f[1<<21],sum[29][29];
int main(){
    n=Read();
    for(LL i=1;i<=n;++i){
        a[i]=Read();
        ++cnt[a[i]];
        for(LL j=1;j<=20;++j){
            if(j==a[i]) continue;
            sum[j][a[i]]+=cnt[j];
        }
    }
    memset(f,inf,sizeof(f));
    f[0]=0;
    LL up=1<<20;
    for(LL i=1;i<up;++i){
        for(LL j=1;j<=20;++j){
            if(!((1<<j-1)&i)) continue;
            LL nw(0);
            LL pre(i-(1<<j-1));
            for(LL k=1;k<=20;++k){
                if(k==j) continue;
                if(!((1<<k-1)&i)) continue;
                nw+=sum[j][k];
            }
            f[i]=std::min(f[i],f[pre]+nw);
        }
    }
    printf("%lld\n",f[up-1]);
    return 0;
}

F

挖个坑，顺便奶一口CSP考2-sat