2019牛客多校第二场F Partition problem（暴搜）题解

题意：把2n个人分成相同两组，分完之后的价值是val(i, j)，其中i属于组1, j属于组2，已知val表，n <= 14

思路：直接dfs暴力分组，新加的价值为当前新加的人与不同组所有人的价值。复杂度$O(C_{2n}^n * n)$。

大概6e8这样子，

代码：

#include<cmath>

#include<set>

#include<map>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 30 + 5;

const int M = 50 + 5;

const ull seed = 131;

const int INF = 0x3f3f3f3f;

const int MOD = 1000000007;

int n;

int t1[20], t2[20];

ll v[maxn][maxn];

ll ans;

void dfs(int pos, int cnt1, int cnt2, ll ret){

    if(cnt1 == cnt2 && cnt1 == n){

        ans = max(ans, ret);

        return;

    }

    ll tmp = 0;

    if(cnt1 < n){

        for(int i = 0; i < cnt2; i++){

            tmp += v[pos][t2[i]];

        }

        t1[cnt1] = pos;

        dfs(pos + 1, cnt1 + 1, cnt2, ret + tmp);

    }

    tmp = 0;

    if(cnt2 < n){

        for(int i = 0; i < cnt1; i++){

            tmp += v[pos][t1[i]];

        }

        t2[cnt2] = pos;

        dfs(pos + 1, cnt1, cnt2 + 1, ret + tmp);

    }

}

int main(){

    scanf("%d", &n);

    ans = 0;

    for(int i = 0; i < 2 * n; i++){

        for(int j = 0; j < 2 * n; j++){

            scanf("%lld", &v[i][j]);

        }

    }

    dfs(0, 0, 0, 0);

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

    return 0;

}

巴特西

2019牛客多校第二场F Partition problem（暴搜）题解

最新文章

热门文章