题解

把 $2n$ 个人分成 $n+n$ 两组，那么一共是 ${2n \choose n}$ 种情况，如果每一次都暴力计算竞争力总和，那么每一次的时间复杂度将是 $O(n^2)$ ，总时间复杂度是 $O({\rm C}_{2n}^{n} \times n^2)$ ，对于 $n \leq 14$ 这个数据范围来说是过不去的。

考虑如何惰性计算这个竞争力总和，也就是说从状态 $A$ 转移到状态 $B$ 的时候根据状态的变化来计算贡献，这是一个常用的思路。

起初，我尝试讨论第 $i$ 个元素是被分到哪一组，元素 $x$ 加入 $A$ 组对总和的贡献就是 $\sum_{i \neq x} v_{ix}$ ，加到一个变量里求和即可，渐进时间复杂度 $O({\rm C}_{2n}^{n} \times n)$ ，但是可能由于姿势不当TLE了。后来在题解中看到了一种思路类似的解法——算贡献的时候不用加，用减。假设当前没有分组的变量的竞争值就是 $\sum_{i=1}^{n} \sum_{j = i+1}^{n} v_{ij}$ ，每次将一个元素分到某一组后，这个元素和原来这个组里的所有元素的贡献需要减去，那么在 $n+n$ 全分配完之后得到的这个变量的值就是还没有被“割断”的“边”。这样做有个好处就是有一个可以减枝的条件：如果当前还没有被“割断”的“边”的总和已经小于当前的最大值了，这条路就没有必要继续枚举了，所以在同是 $O({\rm C}_{2n}^{n} \times n)$ 的复杂度的情况下，这个算法快了很多，1676/4000ms。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAX_N = 14 * 2 + 5;

int n, tot;
int v[MAX_N][MAX_N];
int a[MAX_N], aPtr, b[MAX_N], bPtr;

LL sum, maxAns = -1;

void dfs(int x, int cnt) {
    if (sum < maxAns) return;
    if (cnt > n || cnt + (tot - x + 1) < n) return;
    if (x == tot + 1) {
        maxAns = max(maxAns, sum);
        return;
    }
    LL contribute;

    contribute = 0;
    for (int i = 1; i <= aPtr; ++i) contribute -= v[x][a[i]];
    a[++aPtr] = x; sum += contribute;
    dfs(x + 1, cnt + 1);
    --aPtr; sum -= contribute;

    contribute = 0;
    for (int i = 1; i <= bPtr; ++i) contribute -= v[x][b[i]];
    b[++bPtr] = x; sum += contribute;
    dfs(x + 1, cnt);
    --bPtr; sum -= contribute;
}

int main() {
    scanf("%d", &n);
    tot = (n << 1);

    for (int i = 1; i <= tot; ++i) {
        for (int j = 1; j <= tot; ++j) {
            scanf("%d", &v[i][j]);
            sum += (i < j) * v[i][j];
        }
    }

    dfs(1, 0);

    printf("%lld\n", maxAns);

    return 0;
}

2019牛客多校第二场F（题解）

题解

我的博客