题意:给n, 接下来2*n行,每行2*n列,aij表示第i个人对不在同一队的人的竞争值
要求分出n个人一组,求这一组的最大竞争值。
题解: 爆搜,算出一个人总的竞争值d[i],每次把他加入一组,就加上d[i]减去两倍的所有组内竞争值。
为什么是两倍,假设1,2两个人, 1一开始入队,加上了1和2的竞争值,2入队,就要减去一开始加上的以及d[2]内包含的
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[30][30];
ll d[30];
vector<int> v;
ll n,ans;
void dfs(int p,ll sum){
if(v.size()==n){
ans = max(ans,sum);
return ;
}
if(p>2*n)return ;
ll now = d[p];
for(int i=0;i<v.size();i++){
now-=2*a[p][v[i]];
}
v.push_back(p);
dfs(p+1,sum+now);
v.pop_back();
dfs(p+1,sum);
}
int main()
{
ans= 0;
scanf("%lld",&n);
for(int i=1;i<=2*n;i++){
for(int j=1;j<=2*n;j++){
scanf("%lld",&a[i][j]);
d[i]+=a[i][j];
}
}
dfs(1,0);
printf("%lld",ans);
return 0;
}