CodeForces585 E. Marbles tutorial算法日常[30/100]
1250 words
3 minutes
题目链接
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版)
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#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代码(简洁版)
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
|
#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 指数的
每天一句叨叨
自然界没风风雨雨，大地就不会春华秋实。
