2023-07-25 16:12:57 洛谷题解
思路
看到这道题是统计相邻交换之后操作次数，我第一反应就是求逆序对。
考虑最淳朴的暴力做法，枚举颜色之前的大小顺序关系，然后每次做一次求逆序对，复杂度 \(O(n\log n |c|!)\) (\(|c|\) 表示颜色种类数)。
但是光是 \(20!\) 都有 \(2,432,902,008,176,640,000\) 的大小，再乘上本来就已经卡到 \(10^7\) 的 \(n\log n\)，跑 \(7,000,000\) 个世纪都不一定跑的完。
发现这个巨大的复杂度是因为我们考虑了所有颜色之前的顺序关系，因此我们不需要考虑全部颜色之间的关系，只需要关注颜色两两之间的关系。我们不难发现把所有颜色块合并之后，两个颜色之间的位置关系是唯一的，即对于不同颜色 \(i,j\)，合并之后所有颜色为 \(i\) 的要么全部在颜色为 \(j\) 的左侧，要么全部在右侧 不是废话吗。
所以我们考虑预处理颜色两两之间的关系造成的贡献，然后两两之间统计答案，这个过程的复杂度为 \(O(n|c|^2)\)。
令 \(w[i][j]\) 表示在去掉其他所有颜色的情况下，颜色 \(i\) 全部移动到颜色 \(j\) 左侧对答案的最少贡献。
这个时候我们只需要一个颜色一个颜色的加，把这个颜色的块全部放到左边（右边也行），然后在新加一块之前，我们只需要计算这个颜色与前面所有颜色之间的贡献和再加上前面的所有颜色对答案的贡献即可。
发现前面答案最优推出后面的答案也最优，并且状态数很少，考虑状压 dp。
我们令 \(f[S]\) 表示已插入状态为 \(S\) 时对答案的最小贡献，那么我们可以得到以下转移：
\(f[S]=min(f[S-i]+\sum \limits_{j\in S,j!=i}w[j][i]) \ (i\in S)\)。
\(\sum \limits_{j\in S,j!=i}w[j][i]\) 是复杂度瓶颈，可以通过 \(O(|c|^2)\) 预处理 \(sum[i]\) 解决。
总复杂度 \(O(2^{|c|}|c|^2+|c|^2n)\)，虽然有点卡，但是常数优化以后在 CodeForces 少爷机上也能在 \(1s\) 内跑完。
结合代码理解可能会更简单哦~
\(Code\)
int n,a[400005],b[22][400005];//b[c][i],表示i前面有多少个颜色为c的珠子
ll w[22][22],f[1<<20],sum[22];
int main(){
n=read();
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++){
a[i]=read();
b[a[i]][i]++;
for(int j=1;j<=20;j++){
b[j][i]+=b[j][i-1];//前缀和优化
}
}
for(int l=1;l<=20;l++){
f[1<<l-1]=0;
for(int r=1;r<l;r++){//两边一起加，常数减半
for(int i=1;i<=n;i++){
if(a[i]==l)w[l][r]+=b[r][i];
else if(a[i]==r)w[r][l]+=b[l][i];
}
}
}
for(int s=3;s<(1<<20);s++){
if(__builtin_popcount(s)<2)continue;
for(int i=1;i<=20;i++){
if(!(s&(1<<i-1)))continue;
for(int j=1;j<i;j++){//细节两边一起加，常数砍半
if(!(s&(1<<j-1)))continue;
sum[i]+=w[j][i];
sum[j]+=w[i][j];
}
}
for(int i=1;i<=20;i++){
if(!(s&(1<<i-1)))continue;
f[s]=min(f[s^(1<<i-1)]+sum[i],f[s]);
sum[i]=0;
}
}
cout<<f[(1<<20)-1];
}