Codeforces 1215E 状压DP-蒲公英云

Codeforces 1215E 状压DP

题意：给你一个序列，你可以交换序列中的相邻的两个元素，问最少需要交换多少次可以让这个序列变成若干个极大的颜色相同的子段。

思路：由于题目中的颜色种类很少，考虑状压DP。设dp[mask]为把mask为1的颜色从后往前放置的最小花费。那么我们新添加一种颜色时需要知道要转移多少次，所以我们需要预处理转移矩阵c[i][j]。c[i][j]的意思是只考虑i, j两种元素，把所有的元素i移动到元素j前面的最小花费，预处理好之后暴力转移即可。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 400010;
vector<int> b[20];
int a[maxn];
LL f[1 << 20];
LL c[20][20];
int main() {
    int n;
    scanf("%d", &n);
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[a[i] - 1].push_back(i);
    }
    for (int i = 0; i < 20; i++) {
        if(!b[i].size()) continue;
        for (int j = 0; j < 20; j++) {
            if(!b[j].size() || i == j) continue;
            int p = 0;
            for (int k = 0; k < b[i].size(); k++) {
                while(p < b[j].size() && b[j][p] < b[i][k]) p++;
//                if(p < b[j].size())
                    c[i][j] += p;
            }
        }
    }
    f[0] = 0;
    for (int i = 0; i < (1 << 20); i++) {
        vector<int> d;
        d.clear();
        for (int j = 0; j < 20; j++) {
            if((i >> j) & 1) {
                d.push_back(j);
            }
        }
        for (int j = 0; j < 20; j++) {
            if(((i >> j) & 1) == 0) {
                LL sum = 0;
                for (int k = 0; k < d.size(); k++) {
                    sum += c[d[k]][j];
                }
                f[i ^ (1 << j)] = min(f[i ^ (1 << j)], f[i] + sum);
            }
        }
    }
    printf("%lld\n", f[(1 << 20) - 1]);
}