2019牛客暑期多校训练营（第二场）F（搜索）题意：代码：

题意：

有(2*n)个人，两两之间都有一个权值(v_{ij})。现在要把这(2*n)个人分成两个大小为(n)的集合。定义总价值的大小为：任意两个不在同一阵营的人的权值之和。问你如何划分集合，使得总价值最大，求出最大的总价值。

题解：

因为现在有两个集合(A)，(B)，故我们考虑将两个集合分开讨论。因为(A)，(B)的总数不变，故倘若我们枚举集合(A)的选择的个数，那么显然集合(B)需要选择哪些数也就被唯一确定了。我们考虑用只枚举(A)集合的选取状态，这样的话我们可以通过(mathcal{O}(binom{2*n}{n}))的时间复杂度将A的所有状态进行枚举出来。之后我们考虑如果快速进行答案的更新。

因为我们只考虑枚举(A)集合的状态，且最开始(A)集合的状态为(1)，那么，之后的过程必定是要选取(B)集合中的某一个数加到(A)集合中，假设我们现在要将原本在(B)集合中的(a_i)加到(A)集合中。那么显然，我们只需要将(a_i)原来跟(A)集合中的所有点点贡献删除，并增加现在在(B)集合中的点跟(a_i)的贡献。故此时，我们直接可以用(mathcal{O}(n))的时间复杂度进行更新答案。

至此，整体的时间复杂度为(mathcal{O}(binom{2*n}{n}*n))。这个时间复杂度其实还是非常接近时限的，因此我们还是可以再增加一些必要的剪枝使得它跑得更快。

代码：

#include <bits/stdc++.h>
#define maxn 40
using namespace std;
typedef unsigned long long ll;
ll res=0;
int n,v[maxn][maxn];
//sta是状压了一个2*n位的二进制位，代表当前A集合选取的状态，若当前位为1则代表选1
//cnt代表A选取了的状态
//pre代表当前已经选了前pre个点
//cost代表贡献
void dfs(int sta,int cnt,int pre,ll cost){
if(cnt==n/2){ //两边集合相同，更新答案
res=max(res,cost);
return;
}
if(n-pre-1+cnt<n/2) return; //剪枝，如果发现A集合的数量大于B集合的数量，直接终止
for(int i=pre+1;i<n;i++){ //枚举当前需要将第i个点加到A集合中
ll cur=cost;
for(int j=0;j<n;j++){
if(sta&(1<<j)) cur-=v[i][j]; //如果在原来的状态下第j位是处在A集合中，则直接减去第i个点在第j个点的贡献
else cur+=v[i][j]; //如果在原来的状态下第j位是处在B集合中，则直接加上第i个点在第j个点的贡献
}
dfs(sta|(1<<i),cnt+1,i,cur);
}
}
int main()
{
scanf("%d",&n);
n<<=1;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&v[i][j]);
for(int i=0;i<n;i++){
res+=v[0][i];
}
dfs(1,1,0,res);
printf("%llun",res);
return 0;
}