题解 CF1215E 【Marbles】
x义x
2019-09-16 14:43:18
首先，众所周知，把一个序列变为不降所需要的相邻元素交换次数就是这个序列的逆序对数。这题显然与这个结论有关。
那么这题要我们干的是什么呢？就是按颜色变为不降，只不过颜色的大小顺序我们可以任意指定而已。比如样例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)$对数。这个预处理一下就好了。
代码如下：
```cpp
#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;
}
```