题意:
有 2*n 个人，要把2*n个人平均分配到红队和白队，现在输入一个2n * 2n的矩阵， 第a行第b列代表 第a个人在红队，第b个人在白队的所产生竞争价值，定义竞争价值总和为所有不在同一队的两个队员的竞争价值总和，现在要你求出最大竞争价值总和。
题目链接：
https://ac.nowcoder.com/acm/contest/882/F
题解：
直接暴力DFS， 时间复杂度 最大C(n, 2*n) * n
AC_code:
/*
Algorithm:
Author: anthony1314
Creat Time:
Time Complexity:
*/
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
using namespace std;
int n;
int t1[20], t2[20];
ll v[maxn][maxn];
ll ans;
void dfs(int pos, int cnt1, int cnt2, ll ret){
if(cnt1 == cnt2 && cnt1 == n){
ans = max(ans, ret);
return;
}
ll tmp = 0;
if(cnt1 < n){
for(int i = 0; i < cnt2; i++){
tmp += v[pos][t2[i]];
}
t1[cnt1] = pos;
dfs(pos + 1, cnt1 + 1, cnt2, ret + tmp);
}
tmp = 0;
if(cnt2 < n){
for(int i = 0; i < cnt1; i++){
tmp += v[pos][t1[i]];
}
t2[cnt2] = pos;
dfs(pos + 1, cnt1, cnt2 + 1, ret + tmp);
}
}
int main(){
scanf("%d", &n);
ans = 0;
for(int i = 0; i < 2 * n; i++){
for(int j = 0; j < 2 * n; j++){
scanf("%lld", &v[i][j]);
}
}
dfs(0, 0, 0, 0);
printf("%lld\n", ans);
return 0;
}
