CodeForces585 E. Marbles tutorial算法日常[30/100]

题目链接

CodeForces585 E. Marbles

题意

• 有一排有色石头,然后把相同颜色排在一起
• 能做的操作是交换相邻的石头
• 求最少的操作次数
• n $\in$ [2,4⋅$10^5$]
• $a_i$ $\in$ [1,20]

题解

总体思路

• 看到 $a_i$ $\in$ [1,20],所以算法从 $a_i$ 下手,也就是说对每种颜色下手
• 通过cnt[i][j]计算出把所有的i颜色的放到j颜色前面需要做的这两种颜色之间的交换次数
• 然后用子集dp来递推出最后的答案,就是说一开始是0种颜色之间的关系,然后慢慢得加入各种颜色进去
• 每次加入一种颜色的时候就是把新的颜色放到最后面,然后这样子一直求出所有颜色放入后的最优决策,而且不重不漏!
• 子集dp:
  • 这里的状态就是,dp[$i_{1到1<<20-1}$]
  • 数字i的每一个0,1字符代表着此状态下某种颜色是否存在
  • dp[i]就是状态i的swap数量
  • 就是枚举所有的状态,然后向着添加各种尚未存在的颜色放到最后面的操作来进行dp转移,从子集推向更大的状态集

为什么这样可以不重不漏?

• 因为我们for(1<<20-1) for(20) 的双重循环,就是已经枚举了所有的已经存在的颜色状态,然后把新的颜色放到最后的方案!
• 比如红黄蓝,在 红黄 状态时会有 加入蓝 (蓝在最后),同理也有 红蓝 + 黄,黄蓝 + 红! 这样就达到了不重不漏

英文的tutorial

当然也可以去官方自己看,233

AC代码(tutorial版)

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1000 * 1000 + 13;
const int M = 20 + 1;
const long long INF = 1000 * 1000 * 1000 * 1ll * 1000 * 1000 * 1000;

int n;
long long d[(1 << M)];
long long cnt[M][M];
vector<int> col[M];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        x--;
        col[x].push_back(i);
    }
    // 题解前面的操作有点繁杂,所以推荐看不懂的可以看简单版AC代码
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            if (i == j) {
                continue;
            }
            if ((int)col[i].size() == 0 || (int)col[j].size() == 0) {
                continue;
            }
            int pos2 = 0;
            for (int pos1 = 0; pos1 < (int)col[i].size(); pos1++) {
                // 找到 j 在 i 的每个位置之前的位置.然后计算移动所需要的值(注意这里只要考虑两者之间的交换)
                while (true) {
                    if (pos2 == (int)col[j].size() - 1 || col[j][pos2 + 1] > col[i][pos1]) {
                        break;
                    }
                    pos2++;
                }
                if (col[i][pos1] > col[j][pos2]) {
                    cnt[i][j] += pos2 + 1;
                }
            }
        }
    }

    for (int mask = 0; mask < (1 << 20); mask++) {
        d[mask] = INF;
    }
    d[0] = 0;
    for (int mask = 0; mask < (1 << 20); mask++) {
        vector<int> was;
        for (int i = 0; i < 20; i++) {
            if (mask & (1 << i)) {
                was.push_back(i);
            }
        }
        for (int i = 0; i < 20; i++) {
            if (mask & (1 << i)) {
                continue;
            }
            long long sum = 0;
            for (int j = 0; j < (int)was.size(); j++) {
                sum += cnt[was[j]][i];
            }
            int nmask = mask | (1 << i);
            d[nmask] = min(d[nmask], d[mask] + sum);
        }
    }
    cout << d[(1 << 20) - 1] << endl;
}

AC代码(简洁版)

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

#define MAXN 400010

int n, a[MAXN], cnt[21];
long long inv[21][21], f[(1 << 21) + 1];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        for (int j = 1; j <= 20; ++j) inv[a[i]][j] += cnt[j];
        ++cnt[a[i]];
    }
    for (int i = 1; i < (1 << 20); ++i) f[i] = 1ll << 62;
    // 20种排列要全面枚举出来
    for (int i = 0; i < (1 << 20); ++i) {
        vector<int> x;
        for (int j = 1; j <= 20; ++j)
            if (i & (1 << (j - 1))) x.push_back(j);
        // 这是"我为人人"的子集DP
        for (int j = 1; j <= 20; ++j) {
            if (i & (1 << (j - 1))) continue;
            long long res = 0;
            for (auto k : x) res += inv[k][j];
            long long next_state = i | (1 << (j - 1));
            f[next_state] = min(f[next_state], f[i] + res);
        }
    }
    printf("%I64d\n", f[(1 << 20) - 1]);
}

单词学习

exponential 指数的

每天一句叨叨

自然界没风风雨雨，大地就不会春华秋实。