19牛客多校（第二场）F Partition problem

题目描述

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
0 3
3 0

	
	

		
		

			
			

				#include<bits/stdc++.h>
			

			

				usingnamespacestd;
			

			

				intar[17], br[17];
			

			

				intmp[30][30], n; longlongans = 0;
			

			

				intacnt = 0, bcnt = 0;
			

			

				voidgo(intpos, longlongres) {
			

			

				    if(pos >= 2 * n) {
			

			

				        ans = max(res, ans);
			

			

				        return;
			

			

				    }
			

			

				    if(acnt < n) {
			

			

				        ar[++acnt] = pos;
			

			

				        longlongtmp = 0;
			

			

				        for(inti = 1; i <= bcnt; i++) {
			

			

				            tmp += mp[pos][br[i]];
			

			

				        }
			

			

				        go(pos + 1, res + tmp);
			

			

				        --acnt;
			

			

				    }
			

			

				    if(bcnt < n) {
			

			

				        br[++bcnt] = pos;
			

			

				        longlongtmp = 0;
			

			

				        for(inti = 1; i <= acnt; i++) {
			

			

				            tmp += mp[pos][ar[i]];
			

			

				        }
			

			

				        go(pos + 1, res + tmp);
			

			

				        --bcnt;
			

			

				    }
			

			

				}
			

			

				intmain() {
			

			

				    scanf("%d", &n);
			

			

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

			

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

			

				            scanf("%d", &mp[i][j]);
			

			

				        }
			

			

				    }
			

			

				    go(0, 0LL);
			

			

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

			

				    return0;
			

			

				}
			

			

				/*
			

			

				2
			

			

				0 1 2 3
			

			

				1 0 4 5
			

			

				2 4 0 6
			

			

				3 5 6 0
			

			

				 
			

			

				*/