2019牛客暑期多校训练营（第二场）-F artition problem

题目链接：https://ac.nowcoder.com/acm/contest/882/F

题意：将2×n个人分成两组，每组n个人，求一个组中所有人和另外一组的所有人的竞争值之和。

思路：

　　比赛时看错题了，以为求得是每一队人的竞争值之和，写了两个小时，提交时以为会T，结果一直WA，自闭。。

　　看懂题后，就开始T了。。

　　n<=14，用搜索+剪枝是可以做的。搜索有C(2*n,n)的复杂度，但每种结果需要O(n*n)的复杂度来计算，总复杂度为O(n*n*C(2*n,n))，肯定会T。

　　优化：简化计算结果，先预处理每一行的和v2，v2[i]即第i个人和其它所有人的竞争值的和，用vector存储已经选过的人，选择下一个人x时，用v2[i]减去2×（所有的v1[x][i]），i是已经选过得人的编号，乘2是因为之前加入i时没有减。这样复杂度就降为O(n*C(2*n,n))，因为题目给了4s，是可以过的。

　　　　　另外，可以把第1个人直接选上，因为第1个人肯定要被其中1个队选上，结果一样，这样能将复杂度减1倍。

　AC代码：

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long LL;
int n;
LL v1[30][30],v2[30],ans;
vector<int> vc;

void dfs(int x,LL sum){
    if(vc.size()==n){
        if(sum>ans) ans=sum;
        return;
    }
    if(x>2*n) return;
    LL tmp=v2[x];
    for(int i=0;i<vc.size();++i)
        tmp-=2*v1[x][vc[i]];
    vc.push_back(x);
    dfs(x+1,sum+tmp);
    vc.pop_back();
    dfs(x+1,sum);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=2*n;++i)
        for(int j=1;j<=2*n;++j)
            scanf("%lld",&v1[i][j]),v2[i]+=v1[i][j];
    vc.push_back(1);
    dfs(2,v2[1]);
    printf("%lld
",ans);
    return 0;
}