题解

把个人分成两组，那么一共是种情况，如果每一次都暴力计算竞争力总和，那么每一次的时间复杂度将是，总时间复杂度是，对于这个数据范围来说是过不去的。

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

起初，我尝试讨论第个元素是被分到哪一组，元素加入组对总和的贡献就是，加到一个变量里求和即可，渐进时间复杂度，但是可能由于姿势不当TLE了。后来在题解中看到了一种思路类似的解法——算贡献的时候不用加，用减。假设当前没有分组的变量的竞争值就是，每次将一个元素分到某一组后，这个元素和原来这个组里的所有元素的贡献需要减去，那么在全分配完之后得到的这个变量的值就是还没有被“割断”的“边”。这样做有个好处就是有一个可以减枝的条件：如果当前还没有被“割断”的“边”的总和已经小于当前的最大值了，这条路就没有必要继续枚举了，所以在同是的复杂度的情况下，这个算法快了很多，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;
}

我的博客

www.cfzhao.com
(欢迎大佬们py友链啊！)