Partition problem

解题思路

假设当前两队的对抗值为s，如果把红队中的一个人a分配到白队，s+= a对红队中所有人的对抗值，s-= a对白队中所有人的对抗值。所以我们可以先假设所有人都在红队中，把人一个一个分配到白队中，枚举所有的情况求最大值。

然后继续剪枝：

1.我们可以让1是固定在白队。

2.在搜索的过程中让序号递增，以此来避免重复枚举。

3.保证剩下的的人数足够选择，不够的必然不行。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int read(){

    int res = 0, w = 0; char ch = 0;

    while(!isdigit(ch)){

        w |= ch == '-', ch = getchar();

    }

    while(isdigit(ch)){

        res = (res << 3) + (res << 1) + (ch ^ 48);

        ch = getchar();

    }

    return w ? -res : res;

}

const int N = 30;

ll a[N][N];

bool in[N];

ll ans;

int n;

void dfs(int x, int c, ll sum)

{

    if(c == n){  //已经选择了n个人到白队

        ans = max(ans, sum);

        return;

    }

    for(int i = x + 1; i <= n + c + 1; i ++){ //保证剩下的够选

        ll temp = sum;

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

            if(in[j])

                sum -= a[i][j];

            else

                sum += a[i][j];

        }

        in[i] = true;

        dfs(i, c + 1, sum);

        in[i] = false;  //回溯

        sum = temp;

    }

}

int main()

{

    cin >> n;

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

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

            a[i][j] = read();

        }

    }

    ll sum = 0;

    in[1] = true;  //1固定在白队

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

        sum += a[1][i];

    dfs(1, 1, sum);

    cout << ans << endl;

    return 0;

}

巴特西

2019牛客多校第二场F-Partition problem（搜索+剪枝）

Partition problem

解题思路

代码如下

最新文章

热门文章