13941번: Kronican

https://www.acmicpc.net/problem/13941

풀이는 http://hsin.hr/coci/contest3_solutions.zip 3번 참조

시간복잡도는 $O(n^2*2^n)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, k, c[20][20], dp[1 << 20];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", c[i] + j);
    for (int i = 1 << n; i--;) {
        dp[i] = 1e9;
        int cnt = 0;
        for (int x = 0; x < n; x++) if (!(1 << x&i)) {
            for (int y = 0; y < n; y++) if (!(1 << y&i) && x^y) dp[i] = min(dp[i], dp[i | 1 << x] + c[x][y]);
            cnt++;
        }
        if (cnt <= k) dp[i] = 0;
    }
    printf("%d", dp[0]);
    return 0;
}