链接：https://ac.nowcoder.com/acm/contest/882/F
来源：牛客网
Given 2N people, you need to assign each of them into either red team or white team such that each team consists of exactly N people and the total competitive value is maximized.
Total competitive value is the summation of competitive value of each pair of people in different team.
The equivalent equation is ∑2Ni=1∑2Nj=i+1(vij if i-th person is not in the same team as j-th person else 0)∑i=12N∑j=i+12N(vij if i-th person is not in the same team as j-th person else 0)
输入描述:
The first line of input contains an integers N. Following 2N lines each contains 2N space-separated integers vijvij is the j-th value of the i-th line which indicates the competitive value of person i and person j. * 1≤N≤141≤N≤14
* 0≤vij≤1090≤vij≤109
* vij=vjivij=vji
输出描述:
Output one line containing an integer representing the maximum possible total competitive value.
示例1
输入
1
0 3
3 0
输出
3 题意：
将n*2个人分为两部分，每一个人与另外一半的每一个人贡献一个权值，求贡献和的最大值。
思路：
暴力搜索，最坏的复杂度是C(2*14,14)，也就是差不多4e7,如果你确定某一个人在第一部分，还可以将复杂度除而2
关于算贡献，你可以选择14*14的复杂度，但是肯定会T
在搜索的时候，如果n=5,那么第一次选在第一部分的人就是 1 2 3 4 5.
第二次选在第一部分的人就是 1 2 3 4 6,可以发现只有一个数字不同。
分析一下，其实在整个搜索的过程中，也会出现很多这样只差一个的数组。
于是，我们可以记录上一个状态，通过上个状态算出当前状态，这样可以减小很多算贡献的复杂度。
就这样，我的代码跑了3700ms之后卡过去了。
#include <bits/stdc++.h>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)+1
#define CLR(x,y) memset((x),y,sizeof(x))
#define fuck(x) cerr << #x << "=" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed = ;
const int maxn = 1e5 + ;
const int mod = 1e9 + ;
int n;
ll mp[][];
bool vis[];
ll MIN;
int v1[];
int v2[];
int prev1[];
int prev2[];
ll prenum = ;
ll C[][];
//C[n][m]就是C(n,m)
int tot;
void init(int N) {
for (int i = ; i < N; i ++) {
C[i][] = C[i][i] = ;
for (int j = ; j < i; j ++) {
C[i][j] = C[i - ][j] + C[i - ][j - ];
C[i][j] %= mod;
}
}
} void dfs(int x, int deep) {//必须>=x开始,已经选了num个人
if (deep == n) {
tot--;
if(tot<){return;}
int cnt1 = ;
int cnt2 = ;
for (int i = ; i <= * n; i++) {
if (vis[i]) v1[++cnt1] = i;
else v2[++cnt2] = i;
}
ll num = prenum;
int pos = ;
for (int i = ; i <= n; i++) {
if (v1[i] != prev1[i]) {
pos = i;
break;
}
}
for (int i = pos; i <= n; i++) {
for (int j = ; j <= n; j++) {
num -= mp[prev1[i]][prev2[j]];
num -= mp[v1[i]][prev1[j]];
}
for (int j = ; j <= n; j++) {
num += mp[v1[i]][v2[j]];
num += mp[v1[j]][prev1[i]];
}
}
MIN = max(MIN, num);
for (int i = ; i <= n; i++) {
prev1[i] = v1[i];
prev2[i] = v2[i];
prenum = num;
}
return ;
}
for (int i = x + ; i <= * n; i++) {
vis[i] = ;
dfs(i, deep + );
if(tot<){return;}
vis[i] = ;
}
}
int main() {
MIN = -;
init();
scanf("%d", &n);
tot=C[*n][n];
tot/=;
for (int i = ; i <= * n; i++) {
for (int j = ; j <= * n; j++) {
scanf("%lld", &mp[i][j]);
}
}
dfs(, );
printf("%lld\n", MIN);
return ;
}