题目链接:uva 11795 - Mega Man‘s Mission
题目大意:给出n,表示有n个敌人,首先给出洛克人的武器(二进制数,表示可以杀死的敌人),然后给出n个敌人的武器,同样是二进制,杀死该敌人后可以获得他的武器,问说一共有多少种击杀顺序。
解题思路:用二进制表示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\n", i, solve()); } return 0; }