19牛客暑期多校 round2 F dfs

dfs

先将所有人都归于一队，之后从一队中取出人放置到另一个队。

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

typedef long long ll;

int n;

const int L = 30;

ll a[L][L];

ll sum[L];

ll ans;

vector<int>v;

void dfs(int x,ll re){

	int len = v.size();

	if(len == n){ans = ans>re?ans:re;return;}//队满

	if(x>2*n) return;//越界

	if(x >n + 1 + len) return;//即使将剩下的人全部划分到另一队，其人数也不足n

	ll t = sum[x];

	for(auto s:v) t -= a[x][s]*2;

	v.push_back(x);

	dfs(x+1,re + t);

	v.pop_back();

	dfs(x+1,re);

}

int main(){

	scanf(" %d",&n);

	for(int i = 1;i<=n*2;++i)

		for(int j = 1;j<=n*2;++j){

			scanf(" %lld",&a[i][j]);

			sum[i] += a[i][j];

		}

	dfs(1,0);

	printf("%lld\n",ans);

}

巴特西

19牛客暑期多校 round2 F dfs

dfs

最新文章

热门文章