「GFOI Round 3」CF2084G1 Wish Upon a Satellite (Easy Version)

· · 题解

Easy Version

首先，我们有：

f(c) = \begin{cases} \min(c_1, c_k) & k \bmod 2 = 0 \\ \max(c_1, c_k) & k \bmod 2 = 1 \end{cases}

对称地设 g(c) 为调换先后手顺序后的答案，那么：

g(c) = \begin{cases} \max(c_1, c_k) & k \bmod 2 = 0 \\ \min(c_1, c_k) & k \bmod 2 = 1 \end{cases}

证明：考虑归纳。k \le 2 显然成立。对于 k \ge 3，考虑 f(c) 的计算。假设 k 为奇数。若先手选择 2 \le i \le k - 2 递归到 g(c')，那么答案为 \max(c_1, c_k)；若先手选择 i = 1 或 i = k - 1，那么答案 \le \max(c_1, c_k)。其余情况同理。

所以对于一个排列 p_1, p_2, \ldots, p_n：

\begin{aligned} & \sum\limits_{i = 1}^n \sum\limits_{j = i}^n f([p_i, p_{i + 1}, \ldots, p_j]) \\ = & \sum\limits_{i = 1}^n \sum\limits_{j = i}^n \Big([i \bmod 2 = j \bmod 2] \max(p_i, p_j) + [i \bmod 2 \ne j \bmod 2] \min(p_i, p_j)\Big) \\ = & \sum\limits_{i = 1}^n \sum\limits_{j = i}^n \max(p_i, p_j) - [i \bmod 2 \ne j \bmod 2] (\max(p_i, p_j) - \min(p_i, p_j)) \\ = & \sum\limits_{i = 1}^n i^2 - \sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n [i \bmod 2 \ne j \bmod 2] |p_i - p_j| \end{aligned}

所以现在的问题变成了最小化以下式子：

\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n [i \bmod 2 \ne j \bmod 2] |b_i - b_j|

这个问题可以进一步变成：有一个 1 \sim n 的数轴，点 i 可能是黑色、白色或未确定。若 i 在 a 中的位置为奇数就是黑色，为偶数就是白色，在 a 中未出现则为不确定。我们现在要把未确定的点染成黑色或者白色，使得：

所有不同颜色点对的距离之和可以变成：对于所有 1 \le k < n，1 \sim k 中的黑点数量乘 k + 1 \sim n 的白点数量加上 1 \sim k 中的白点数量乘 k + 1 \sim n 的黑点数量之和。

这个简化后的问题可以 DP 了。设 f_{i, j} 表示已经确定了 1 \sim i 中的点的颜色，其中有 j 个黑点，对于所有 1 \le k < i 上述式子的和的最小值。

至于转移，考虑先将 f_{i, j} 加上 k = i 时上述式子的值，即将所有 f_{i, j} 加上 j \times (\left\lfloor\frac{n}{2}\right\rfloor - (i - j)) + (i - j) \times (\left\lceil\frac{n}{2}\right\rceil - j)。

然后考虑第 i + 1 个点是黑点或者白点。

最后的答案即为 \sum\limits_{i = 1}^n i^2 - f_{n, \left\lceil\frac{n}{2}\right\rceil}。

时间复杂度：每组测试用例 O(n^2)。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1, -1);
    vector< vector<ll> > f(n + 1, vector<ll>(n + 1, 1e18));
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        if (x) {
            a[x] = i & 1;
        }
    }
    if (a[1] != 1) {
        f[1][0] = 0;
    }
    if (a[1] != 0) {
        f[1][1] = 0;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            f[i][j] += j * (n / 2 - (i - j)) + (i - j) * ((n + 1) / 2 - j);
            if (a[i + 1] != 1) {
                f[i + 1][j] = min(f[i + 1][j], f[i][j]);
            }
            if (a[i + 1] != 0) {
                f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]);
            }
        }
    }
    ll ans = -f[n][(n + 1) / 2];
    for (int i = 1; i <= n; ++i) {
        ans += i * i;
    }
    cout << ans << '\n';
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}