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

发布于 2019-07-23  277 次阅读


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

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

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
using namespace std;
typedef long long ll;
int n;
ll ans = 0;
int acnt = 0, bcnt = 0;//a b组当前人数
ll arr[30][30];
int a[15], b[15];//a b组人的编号

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;
}

愿风指引你的道路,愿你的刀刃永远锋利。