Codeforces 第 995 轮 G 题

January 2, 2025

问题链接: Codeforces Round 995 Problem G

首先，注意题目约束如下：

第一行包含两个整数 $n$ 和 $q$ ( $1≤ n ≤20$ ; $1 ≤ q ≤ 2 \cdot 10^5$ ) — 蛇的数量和事件的数量。

这意味着我们可以使用关于 $n$ 复杂度较高的算法，因为 $n$ 只有20。

由于我们知道蛇的放置顺序，我们只需要知道任意两条蛇之间的最小距离。为此，我们可以假设两条蛇在开始时是相邻的。我们可以用两个变量来存储蛇的位置。左边的蛇在位置 $x$ ，右边的蛇在位置 $y$ 。初始时，设置 $x = 0$ 和 $y = 1$ 。然后我们以 $O(q)$ 的时间复杂度扫描所有移动。

如果左边的蛇变大，我们将其向右移动 ( $x += 1$ )。如果右边的蛇缩小，我们也将其向右移动 ( $y += 1$ )。如果 $x = y$ ，这意味着两条蛇相遇了，我们需要增加它们之间的距离。增加距离后，我们可以将左边的蛇向右移动 ( $x += 1$ )，或者将右边的蛇向右移动 ( $y += 1$ )。

使用这个算法，我们可以用 $O(n^2 q)$ 的时间复杂度计算所有蛇之间的最小距离。

(注意：以下C++代码片段中计算 min_dist 的逻辑可能存在缺陷，因为对蛇缩小的移动规则可能被误解了。这里按最初的思路呈现。)

vector<vector<int>> min_dist(n, vector<int>(n, 1e18));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (i == j) {
            min_dist[i][j] = 0;
            continue;
        }
        int dis = 1;
        int x = 0, y = 1;
        for (auto &ele : v) {
            if (ele.first == i) { x += ele.second == '+' ? 1 : 0; }
            if (ele.first == j) { y += ele.second == '+' ? 0 : 1; }
            if (x == y) {
                dis++;
                x--;
            }
        }
        min_dist[i][j] = dis;
    }
}

问题的第二部分是确定我们应该以什么顺序放置蛇。如果我们使用暴力法来解决这个问题，时间复杂度是 $O(n! n^2 q)$ ，这是不可接受的。我们需要找到一个更好的算法来解决这个问题。

如果我们考虑以下动态规划状态：

mask: 一个位掩码，表示我们已经放置的蛇的集合。
last: 我们在这个集合中最后放置的蛇。

$dp[mask][last]$ 是放置由 mask 表示的蛇所需的最小总长度，其中 last 是最后放置的蛇。

转移函数如下：

dp[mask][last] = \min_{i \in mask, i \neq last} (dp[mask \setminus \{last\}][i] + min\_dist[i][last])

vector<vector<int>> dp(1 << n, vector<int>(n, 1e18)); // `mask` 已放置，最后一个是 `last`
// 初始状态
for (int i = 0; i < n; i++) { dp[1 << i][i] = 1; }
// dp 循环
for (int mask = 1; mask < (1 << n); mask++) {
    for (int last = 0; last < n; last++) {
        if (!(mask & (1 << last))) continue; // `last` 必须在 `mask` 中
        if (mask == (1 << last)) continue; // 基本情况已经初始化
        int prev_mask = mask ^ (1 << last);
        for (int i = 0; i < n; i++) {
            if (prev_mask & (1 << i)) { // 遍历之前的蛇 `i`
                dp[mask][last] = min(dp[mask][last], dp[prev_mask][i] + min_dist[i][last]);
            }
        }
    }
}

最终答案是所有可能的最后一条蛇 $i$ 的 $dp[(1 << n) - 1][i] + \text{enlargement\_of\_i}$ 的最小值。

    long long ans = 1e18;
    // 最后元素的增量
    vector<int> enlargement(n, 0);
    for (auto &ele : v) {
        if (ele.second == '+') {
            enlargement[ele.first]++;
        }
    }

    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[(1 << n) - 1][i] + enlargement[i]);
    }

Transformer 模型详解