2019牛客暑期多校2-Partition problem深搜

1
0 3
3 0

3

ll n,ans = 0;
ll a[40][40];
int sel[40];
ll sum[maxn];
int r = 0;
void dfs(ll curval,int pos){
  if(r == n) {
    ans = max(ans,curval);
    return ;
  }
  if(pos >= 2 * n + 1 || r > n) return ;
  ll s = sum[pos];
  for(int i=1;i<=r;i++){
    int t = sel[i];
    s -= 2 * a[pos][t];
  }
  r ++;
  sel[r] = pos;
  dfs(curval + s,pos+1);
  r --;
  dfs(curval,pos+1);
}
int main() {
  n = read;
  for(int i=1;i<=2*n;i++){
    for(int j=1;j<=2*n;j++) a[i][j] = read,sum[i] += a[i][j];
  }
  ans = 0;
  dfs(0,1);
  cout << ans <<endl;
  return 0;
}