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[][],v2[],ans;

vector<int> vc;

void dfs(int x,LL sum){

    if(vc.size()==n){

        if(sum>ans) ans=sum;

        return;

    }

    if(x>*n) return;

    LL tmp=v2[x];

    for(int i=;i<vc.size();++i)

        tmp-=*v1[x][vc[i]];

    vc.push_back(x);

    dfs(x+,sum+tmp);

    vc.pop_back();

    dfs(x+,sum);

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=*n;++i)

        for(int j=;j<=*n;++j)

            scanf("%lld",&v1[i][j]),v2[i]+=v1[i][j];

    vc.push_back();

    dfs(,v2[]);

    printf("%lld\n",ans);

    return ;

}

巴特西

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

最新文章

热门文章