MAUGIAO - The problem for kid

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<climits>

const int N = 20;
int f[1 << N], a[N][N], n;
long long c[1 << N];

void enter() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			scanf("%d", &a[i][j]);
}

int snoob(const int &x) {
	int r = x & -x, h = x + r;
	return h | (x ^ h) / r >> 2;
}

void solve() {
	const int Omega = 1 << n;
	f[0] = 0; c[0] = 1;
	for(int i = 0; i < n; ++i)
		for(int s = (1 << (i+1)) - 1; s < Omega; s = snoob(s)) {
			f[s] = INT_MIN;
			for(int p = 0; p < n; ++p) if(s & 1 << p) {
				const int ss = s & ~(1 << p);
				if(f[ss] + a[i][p] > f[s]) {
					f[s] = f[ss] + a[i][p];
					c[s] = c[ss];
				} else if(f[ss] + a[i][p] == f[s])
					c[s] += c[ss];
			}
		}
	printf("%d %lld\n", f[Omega - 1], c[Omega - 1]);
}

int main() {
	enter();
	solve();
	return 0;
}

Download