兔子组队 题解

嗯。

---

显然暴力枚举每个组的话状态数肯定很多（感觉是 $O(n!)$ 级别的），肯定炸。

注意到这题是蓝题，所以考虑状压 DP。

令 $f(i)$ 为 $i$ 的所有二进制位为 $1$ 的下标组成的集合。

$dp[i]$ 表示当前集合 $f(i)$ 的兔子全都分好组了，其他还没分组。

令 $\text{cont}(s)$ 为兔子集合 $s$ 可以得到的分，则有如下转移方程：

$$dp[i]=\max_{f(j)\in f(i)} dp[j]+\text{cont}(f(i)\oplus f(j))\\$$

显然可以预处理 $\text{cont}(i)$，转移时可以位运算代替集合运算。

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
#define int long long
using namespace std;
int a[16][16];
int cont[1 << 16];
int dp[1 << 16];
int n;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 0; i < (1 << n); i++){
		for(int j = 0; j < n; j++){
			if(~i >> j & 1) continue;
			for(int k = 0; k < j; k++){
				if(~i >> k & 1) continue;
				cont[i] += a[j][k];
			}
		}
	}
	memset(dp, -64, sizeof(dp));
	int ans = 0;
	dp[0] = 0;
	for(int i = 1; i < (1 << n); i++){
		for(int j = 0; j < (1 << n); j++){
			if((i & j) != j) continue;
			dp[i] = max(dp[i], dp[j] + cont[i ^ j]);
		}
		ans = max(ans, dp[i]);
	}
	cout << ans;

	return 0;
}

但是这样的话时间复杂度是 $O((2^n)^2)$，$n=16$ 时会运行约 $2\times 10^9$，会超时。

注意到有很多无效的枚举，可以优化。

当 $f(j)\in f(i)$ 时，对于 $i$ 所有二进制为 $0$ 的位置，$j$ 二进制这个位置一定是 $0$。

所以对于状态 $i$，我们只需要枚举 $i$ 为 $1$ 的二进制位即可，单次枚举次数为 $2^{\text{popcount}(i)}$。

这样可以减小大量的状态数，经过计算可知总状态数约等于 $4\times 10^7$ 个，再乘个配置 $j$ 的 $n$ 也绰绰有余。

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
#define int long long
using namespace std;
int a[16][16];
int cont[1 << 16];
int dp[1 << 16];
int popcount[1 << 16];
int n;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 1; i < (1 << n); i++){
		if(i & 1) popcount[i] = popcount[i >> 1] + 1;
		else popcount[i] = popcount[i >> 1];
	}
	for(int i = 0; i < (1 << n); i++){
		for(int j = 0; j < n; j++){
			if(~i >> j & 1) continue;
			for(int k = 0; k < j; k++){
				if(~i >> k & 1) continue;
				cont[i] += a[j][k];
			}
		}
	}
	memset(dp, -64, sizeof(dp));
	int ans = 0;
	dp[0] = 0;
	for(int i = 1; i < (1 << n); i++){
		for(int j = 0; j < (1 << popcount[i]); j++){
			int tmp = j, val = 0;
			for(int k = 0; k < n; k++){
				if(i >> k & 1){
					val |= ((tmp & 1) << k);
					tmp >>= 1;
				}
			}
			dp[i] = max(dp[i], dp[val] + cont[i ^ val]);
		}
		ans = max(ans, dp[i]);
	}
	cout << ans;

	return 0;
}

时间复杂度：$O(4\times 10^7\times n)$。

其实这个代码还可以优化，可以通过递推来将时间复杂度中的 $n$ 去掉，请大家自行尝试。