[牛客暑期多校第二场][DFS暴力]F-Partition problem

https://ac.nowcoder.com/acm/contest/882/F

虽然是个暴力题。。。但是当时场上过的并不多 我也不是很懂 抄的大佬的 写下注释吧。

#include
#include
#include
#include
#include
#include
#include
#include
#include

void dfs(int pos, ll res) {
if (pos >= 2 * n) {//总人数大于
ans = max(ans, res);//更新答案
return;
}
if (acnt < n) {//A组人数没满
a[++acnt] = pos;//A组acnt号就是当前这个人
ll tmp = 0;
for (int i = 1; i <= bcnt; i++) {
tmp += arr[pos][b[i]];//算出这一行在B组人对A的贡献
}
dfs(pos + 1, res + tmp);//递归 人数多了1 总和加上了上面计算的贡献
acnt–;
}
if (bcnt < n) {
b[++bcnt] = pos;
ll tmp = 0;
for (int i = 1; i <= acnt; i++) {
tmp += arr[pos][a[i]];
}
dfs(pos + 1, res + tmp);
bcnt–;
}
}

int main() {
scanf(“%d”, &n);
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < 2 * n; j++) {
scanf(“%d”, &arr[i][j]);
}
}
dfs(0, 0ll);
printf(“%lld\n”, ans);
return 0;
}