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

链接：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

输入

输出

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 ;

}