题解 | Partition problem-2019牛客暑期多校训练营第二场F题

题目来源于牛客竞赛：https://ac.nowcoder.com/acm/contest/discuss
题目描述：
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 $\sum_{i=1}^{2N}$∑i=12N​$\sum_{j=i+1}^{2N}$∑j=i+12N​(v_ij 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 v_ij is the j-th value of the i-th line which indicates the competitive value of person i and person j.

1≤N≤14
1≤v_ij≤10⁹
v_ij=v_ji

输出描述：
Output one line containing an integer representing the maximum possible total competitive value.

示例1：
输入
1
0 3
3 0

输出
3

题解：
• Brute force
There are C(2N, N) ways of assignments. For each assignment, the cost can be calculated in O(N^2).
Results in O(C(2N, N) N^2) time complexity.

• Brute force
O(C(2N, N) N^2) may NOT be fast enough.
You can solve it in O(C(2N, N) N).
First, put all people in one team. The value will be 0.
Whenever pull one people to another team, we can compute the delta of the value. In each step, it takes O(N).

代码：

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 18;
typedef long long LL;
int n, all;
LL v[N + N][N + N], ans;
void go(int msk, int got, int pre, LL cst) {
  if (got + got == n) {
    ans = max(ans, cst);
    return;
  }
  if (n - pre - 1 + got < n / 2) {
    return;
  }
  for (int nxt = pre + 1; nxt < n; ++ nxt) {
    LL nxt_cst = cst;
    for (int i = 0; i < n; ++i) {
      if ((msk >> i) & 1)
        nxt_cst -= v[nxt][i];
      else
        nxt_cst += v[nxt][i];
    }
    go(msk | (1 << nxt), got + 1, nxt, nxt_cst);
  }
}
int main() {
  cin >> n;
  n <<= 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> v[i][j];
    }
  }
  all = (1 << n) - 1;
  LL cst = 0;
  for (int i = 0; i < n; ++i) {
    cst += v[0][i];
  }
  go((1 << 0), 1, 0, cst);
  printf("%lld\n", ans);
}

更多问题，更详细题解可关注牛客竞赛区，一个刷题、比赛、分享的社区。
传送门：https://ac.nowcoder.com/acm/contest/discuss