UVA 11795 七 Mega Man's Mission

七 Mega Man's Mission
Time Limit:1000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 long long dp[65540];
 7 int enemy[20],weapons[65540];
 8 
 9 int main()
10 {
11     int T,ca=0;
12     int n,mega;
13     char s[20];
14     int i,j,k;
15     scanf("%d",&T);
16     while(T--)
17     {
18         mega=0;
19         memset(dp,0,sizeof(dp));
20         memset(enemy,0,sizeof(enemy));
21         memset(weapons,0,sizeof(weapons));
22 
23         scanf("%d",&n);
24         scanf("%s",s);
25         for(i=0;i<n;i++)
26         {
27             if(s[i]=='1')
28             {
29                 mega=mega | (1 << i);
30             }
31         }
32         for(i=0;i<n;i++)
33         {
34             scanf("%s",s);
35             for(j=0;j<n;j++)
36             {
37                 if(s[j]=='1')
38                 {
39                     enemy[i]=enemy[i] | (1 << j);
40                 }
41             }
42         }
43         for(i=0;i<(1 << n);i++)
44         {
45             weapons[i]=mega;
46             for(j=0;j<n;j++)
47             {
48                 if(i & 1<<j)
49                 {
50                     weapons[i]=weapons[i] | enemy[j];
51                 }
52             }
53         }
54 
55         dp[0]=1;
56         for(i=0;i<(1<<n);i++)
57         {
58             if(dp[i] == 0) continue;
59             for(j=0;j<n;j++)
60             {
61                 if((weapons[i] & (1<<j))!=0 && (i & (1<<j))==0)
62                     dp[i | (1<<j)]=dp[i | (1<<j)]+dp[i];
63             }
64         }
65 
66         printf("Case %d: %lld
",++ca,dp[(1<<n)-1]);
67     }
68     return 0;
69 }
View Code