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

巴特西

CF1215题解

E

F

最新文章

热门文章