题目链接：2019 牛客多校第二场 F
把 \(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。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #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;
}
|