CF1215E. Marbles

发表于 | 阅读数

数组$a_i$,每次可以选择相邻交换位置，求最小操作次数使得最后相同颜色都聚在一起。$n\leq 4\times10^5,c\leq 20$

相邻交换，想到了逆序对。（要将相应的权值移动到对应位置就是$a_i$的逆序对）。有$20$种颜色，显然不可能随机赋予权值$20!$。根逆序对一样。可以发现在计算总逆序对的时候有重复的情况。

设$dp[i]$,$i$的二进制表示，对应颜色已经按某种次序聚在一起(其他颜色默认为空)。如果新加入颜色为$k$,$dp[2^k|i]=min(dp[2^k|i],dp[i]+\sum_{p\in i} f[p][k]$，$f[p][k]$表示将颜色$p$放到颜色$k$前面去所需要的代价。

复杂度$O(2^{20}\times 20^2+20n)$，实际计算复杂度会小很多。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
const int M = 20;

ll f[M][M], dp[1 << M];
int cnt[M], n, k, a[N];
int main()
{
    scanf("%d", &n);
    k = 20;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), a[i]--;
    for (int i = 1; i <= n; i++)
    {
        cnt[a[i]]++;
        for (int j = 0; j < k; j++)
            f[a[i]][j] += cnt[j];
    }
    for (int i = 0; i < (1 << k); i++)
        dp[i] = inf;
    dp[0] = 0;
    for (int i = 0; i < (1 << k); i++)
    {
        for (int j = 0; j < k; j++)
            if (i & (1 << j))
            {
                int ss = i - (1 << j);
                ll mi = 0;
                for (int t = 0; t < k; t++)
                    if (ss & (1 << t))
                        mi += f[t][j];
                dp[i] = min(dp[i], dp[ss] + mi);
            }
    }
    printf("%lld\n", dp[(1 << k) - 1]);
}