UVA-11795 Mega Man's Mission (状压DP)

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 #define M(a) memset(a, 0, sizeof(a))
 5 #define INF 0x3f3f3f3f
 6 const int maxn = (1 << 16) + 10;
 7 int s[maxn], kill[maxn];
 8 long long dp[maxn];
 9 
10 int main() {
11 
12     int T, n, kase = 0;
13     scanf("%d", &T);
14     while(T--) {
15         char str[20];
16         M(dp), M(kill), M(s);
17         scanf("%d%s", &n, str);
18         for (int i = 0; i < n; ++i)
19             if (str[i] == ‘1‘)
20                 kill[0] += (1 << i);
21         for (int i = 0; i < n; ++i) {
22             scanf("%s", str);
23             for (int j = 0; j < n; ++j)
24                 if (str[j] == ‘1‘) 
25                     s[i] |= (1 << j);
26         }
27         int all = (1 << n) - 1;
28         for (int i = 0; i <= all; ++i) {
29             kill[i] = kill[0];
30             for (int j = 0; j < n; ++j)
31                 if (i & (1 << j))
32                     kill[i] |= s[j];
33         }
34         dp[0] = 1;
35         for (int i = 0; i < all; ++i)
36             for (int j = 0; j < n; ++j)
37                 if (((kill[i] & (1 << j))) && !(i & (1 << j)))
38                     dp[i|(1 << j)] += dp[i];
39         printf("Case %d: %lld\n", ++kase, dp[all]);
40     }
41 
42     return 0;
43 }