MAUGIAO - The problem for kid

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#define FOR(i,a,b) for(i = a; i <= b; ++i)
#define REP(i,a) for(i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
using namespace std;

#define TWO(x) (1<<(x))
#define CONTAIN(S,x) (S & TWO(x))
;

int f[1100111], n, a[22][22];
long long g[1100111];
vector<int> ls[22];

int main() {
    int i, mask, j;
    scanf("%d", &n); FOR(i,1,n) FOR(j,1,n) scanf("%d", &a[i][j]);
    f[0] = 0;
    g[0] = 1;

    int cnt;
    REP(mask,TWO(n)) {
        cnt = 0;
        REP(i,n)
            if (CONTAIN(mask,i)) ++cnt;
        ls[cnt].PB(mask);
    }

    int cur, mask2, x, sz;
    FOR(i,0,n-1) {
        sz = ls[i].size();
        REP(x,sz) {
            mask = ls[i][x];
            if (!*(g+mask)) continue;
            REP(j,n) if (!CONTAIN(mask,j)) {
                cur = *(f+mask) + a[i+1][j+1];
                mask2 = mask + TWO(j);
                if (cur > *(f+mask2)) {
                    *(f+mask2) = cur;
                    *(g+mask2) = *(g+mask);
                }
                else if (cur == *(f+mask2))
                    *(g+mask2) += *(g+mask);
            }
        }
    }
    cout << f[TWO(n)-1] << ' ' << g[TWO(n)-1] << endl;
    return 0;
}

Download