题解 CF1215E 【Marbles】

首先，众所周知，把一个序列变为不降所需要的相邻元素交换次数就是这个序列的逆序对数。这题显然与这个结论有关。

那么这题要我们干的是什么呢？就是按颜色变为不降，只不过颜色的大小顺序我们可以任意指定而已。比如样例1指定的就是3<4<2，样例2指定的就是20<1<14<10<2。

看到颜色数最多20，显然是状压DP。定义f[s]是s对应的颜色的大小顺序已经安排好了的最小逆序对数。

假设已经安排好k_1<k_2<\dots<k_m，我们选择一个在s中没出现过的k_{m+1}。那么新的状态就要加上(k_1,k_{m+1})之间的，满足i<j,a_i=k_1,a_j=k_2的(i,j)对数。这个预处理一下就好了。

代码如下：

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

int N,A[400005];
int cnt[25];
ll B[25][25];
ll f[2000005];

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&A[i]);
        for(int j=1;j<=20;j++)
            B[j][A[i]]+=cnt[j];
        cnt[A[i]]++;
    }
    memset(f,63,sizeof(f));
    f[0]=0;
    for(int s=0;s<(1<<20);s++)
    for(int i=1;i<=20;i++)if(!((s>>(i-1))&1)){
        ll tmp=0;
        for(int j=1;j<=20;j++)if((s>>(j-1))&1)
            tmp+=B[j][i];
        f[s|(1<<(i-1))]=min(f[s|(1<<(i-1))],f[s]+tmp);
    }
    printf("%I64d\n",f[(1<<20)-1]);

    return 0;
}