SGU485 Arrays 题解

卡常题。而且似乎数据比较水。

简而言之，我们需要最大化

拆成这个式子：

先固定 ，不妨假设 是按照 从大到小排序。确定最优化的 的顺序。我们要最小化 ，最大化 ，根据排序不等式， 的大小应该和 顺序， 应该和 逆序。

显然 应该大于 ，因而 应当大于等于 。否则交换二者代价由负变正，显然不劣。如果 也小于 ，那么此时交换两者也不劣，原因是交换后 不变， 变大。

此时 和 逆序，也就是说 的最大值小于 的最小值。请注意 和 也是逆序的，因为 和 是顺序的，因此同样 的最大值小于 的最小值。因此， 永远是排序之后最小的 项。

此外， 应该小于 ，否则交换不劣，因为交换后 不变， 变小。在之后的过程里，可以认为 。

我们希望给前面 项进行配对，最大化这个代价。

此时可以考虑状压 DP。把左侧没有配对的 相对当前的 的位置记录到 里，如果 的某一位是 ，说明这个位置是一个未配对的 。每次的转移是选择分配到 还是 。如果是 就并且向左移动一位加上 。否则，根据我们 和 顺序的结论，我们应该取最高的 进行转移。注意仍然需要左移一位更新相对位置。

直接暴力计算所有可能，每层最多 个状态，转移 ，有 层，复杂度 的，显然过不了。实际上，每个位置最左边的 不可能超过 位（从 开始编号）。假设当前的第 位是 并且此时仍然选择分配到 的话，考虑此时 里每一位的状态。

• 如果是 ，那么这是一个未配对的 。
• 如果是 ，说明这个和前面的某个位置配对上了。请注意，由于我们是从高往低配对，因此每个 配对的位置一定是最高的 更前面的数。

我们发现，此时无论是 还是 ，其都占用了一个配对，而一共只有 个配对，此时在分配到 注定是不合法的。因此我们只需要保留最后 位即可。

但是此时每层的状态数仍然高达 。对于 确实难以通过。

不过我们可以敏锐的发现，并非每个状态都是有用的。实际上可能并不能达到 个状态。不妨考虑 的情况，更小的情况这个复杂度是足以通过的。

我们发现，匹配的过程类似括号串，满足前缀 大于等于前缀 。我们保留的相当于一个括号串的子串。考虑用折线法容斥加上这个简单的 python 程序估算一下状态数。

ans = 0
for i in range(14):
     k = 0
     for j in range(25 + 1):
         delta = i - (25 - j - j)
         if delta <= 0:
             continue
         k += math.comb(25, j)
         if j - delta * 2 >= 0:
             k -= math.comb(25, j - delta * 2)

     ans += k
     print(k)

ans *= 2

会发现答案大概是 级别。

实际上这个 仍然远远跑不满，因为我们并不会记录已经配对好的位置。

我们注意到你的状态个数之和 有关，因此你可以写个程序去暴力算出来具体有多少个状态。你会发现峰值是 ，总和大概在 级别。

此时需要精细实现，基本上是带个 就会 TLE 的级别。std::unordered_map 在这种数据范围下会很慢，实测就算只计算状态个数就需要 秒。

实际上你的值域只有 ，开个数组暴力记录下标即可。

但是，本题的空间限制为 。开个 的数组加上 DP 的状态数组很容易 MLE。

我们注意到，每一层的 的个数的奇偶性是相同的，对于 和 ，这两个状态不可能出现在同一层，因为其 的个数的奇偶性发生了改变。因此我们开一半， 次方即可，每次查询下标除以二位置的值即可。

参考代码：

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <vector>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace solve {
const uint npos = -1;

void solve(uint n) {
    std::vector<unsigned short> v(n * 3);

    for (size_t i = 0; i < n * 3; i++) {
        std::cin >> v[i];
    }

    std::sort(v.begin(), v.end(), std::greater<unsigned short>());

    std::vector<unsigned short> cost(v.begin() + 2 * n, v.end());
    std::reverse(cost.begin(), cost.end());
    v.resize(2 * n);

    std::vector<std::pair<uint, uint>> dp;

    dp.emplace_back(0, 0);

    std::vector<uint> real_pos(1 << (n - 1), npos);

    for (uint i = 0; i < 2 * n; i++) {
        std::vector<std::pair<uint, uint>> nxt;
        nxt.reserve(8705686);

        auto update = [&](uint pos, uint val) {
            if (real_pos[pos / 2] == npos) {
                real_pos[pos / 2] = nxt.size();
                nxt.emplace_back(pos, val);
            }
            else {
                nxt[real_pos[pos / 2]].second =
                    std::max(nxt[real_pos[pos / 2]].second, val);
            }
        };

        for (const auto &stat : dp) {
            const uint cnt = __builtin_popcount(stat.first);

            if (cnt != 0) {
                const uint prev_pair = (i - cnt) / 2;
                const uint highbit = 31 - __builtin_clz(stat.first);

                update((stat.first ^ (1 << highbit)) << 1,
                       v[i] * v[i - 1 - highbit] - v[i] * cost[prev_pair] +
                           stat.second);
            }

            if (2 * n - i - 1 < cnt + 1) {
                continue;
            }

            if (!((stat.first >> (n - 1)) & 1)) {
                update((stat.first << 1) | 1, stat.second);
            }
        }

        dp.swap(nxt);
        for (auto &&i : dp) {
            real_pos[i.first / 2] = npos;
        }
    }
    std::cout << dp[0].second << "\n";
    return;
}
} // namespace solve

int main() {
    uint t, n;
    std::cin >> t >> n;
    while (t--) {
        solve::solve(n);
    }
    std::cout << std::flush;
    return 0;
}