AT4132 [ARC097C] Sorted and Sorted

发表于 | 阅读数

有 $2N$个球排成一列，其中有$N$个黑球与 $N$ 个白球。把 $1$ 到 $N$ 这 $N$个数字分别写到 $N$ 个黑球上；白球亦然。左起第 $i$ 个球上的写的数字是 $a_i$，颜色是 $c_i$。

$B$ 是黑球，为 $W$ 是白球。

定义一次操作为交换两个相邻的球。你需要求出最少的操作使得序列中

考虑一个数的交换次数就是他的逆序对，但是这里并没有确定比他小的数。无法直接计算可得

那么显然可以设$dp[i][j]$表示把前$i$个白球放好，前$j$个黑球，那么加入我放$i$这个白球，那么$i-1$个白球以及$j$个黑球就是比他小的，这样就可以计算出逆序对了。同理黑球也是。

  • $i-1$个白球以及$j$个黑球就是比他小的可以预处理就解决了。
代码 
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

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<pair<char, int>> a(2 * n + 1);
    vector<int> pw(n + 1), pb(n + 1);
    for (int i = 1; i <= 2 * n; i++)
    {
        cin >> a[i].first >> a[i].second;
        if (a[i].first == 'W')
            pw[a[i].second] = i;
        if (a[i].first == 'B')
            pb[a[i].second] = i;
    }
    vector<vector<int>> cw(2 * n + 1, vector<int>(n + 1));
    vector<vector<int>> cb(2 * n + 1, vector<int>(n + 1));
    for (int i = 1; i <= 2 * n; i++)
        for (int j = 0; j <= n; j++)
        {
            cw[i][j] = cw[i - 1][j] + (a[i - 1].second > j && a[i - 1].first == 'W');
            cb[i][j] = cb[i - 1][j] + (a[i - 1].second > j && a[i - 1].first == 'B');
        }
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 1e9));
    dp[0][0] = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
        {
            int x = pw[i], y = pb[j];
            if (i)
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + cw[x][i] + cb[x][j]);
            if (j)
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + cw[y][i] + cb[y][j]);
        }
    cout << dp[n][n] << endl;
}