uva 11795 - Mega Man's Mission(dp)

제목 링크: uva 11795 - Mega Man's Mission
제목 대의: n을 제시하면 n개의 적이 있음을 나타낸다. 먼저 로크인의 무기(이진수, 죽일 수 있는 적을 표시)를 제시한 다음에 n개의 적의 무기를 제시한다. 마찬가지로 2진법이다. 이 적을 죽인 후에 그의 무기를 얻을 수 있다. 모두 몇 가지 처치 순서가 있는지 묻는다.
문제풀이 사고방식: 2진법으로 i로 그 사람들이 죽었다고 표시하고, dp[i]는 이 집합된 사람들이 몇 가지 순서가 있는지 표시한다. 그리고 h[i]는 이들의 무기를 획득하면 다른 몇 명을 죽일 수 있는지 표시한다.

#include <stdio.h>
#include <string.h>

typedef long long ll;
const int N = 17;
const int M = 1<<N;

int n, g[N], h[M];
ll dp[M];

int get() {
	char str[M];
	scanf("%s", str);
	int len = strlen(str), ans = 0;
	for (int i = 0; i < len; i++) if (str[i] == '1')
		ans |= (1<<i);
	return ans;
}

void init () {
	scanf("%d", &n);
	h[0] = get();
	for (int i = 0; i < n; i++) g[i] = get();
	for (int i = 0; i < (1<<n); i++) {
		h[i] = h[0];
		for (int j = 0; j < n; j++) if (i & (1<<j)) {
			h[i] |= g[j];
		}
	}
}

ll solve() {
	dp[0] = 1;
	for (int i = 1; i < (1<<n); i++) {
		dp[i] = 0;
		for (int j = 0; j < n; j++) if (i&(1<<j) && h[i^(1<<j)]&(1<<j))
			dp[i] += dp[i^(1<<j)];
	}
	return dp[(1<<n)-1];
}

int main () {
	int cas;
	scanf("%d", &cas);
	for (int i = 1; i <= cas; i++) {
		init();
		printf("Case %d: %lld
", i, solve());
	}
	return 0;
}