light oj 1037 状压dp

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <queue>
 5 #include <cstdio>
 6 #include <algorithm>
 7 #include <map>
 8 //#include <time.h>
 9 //#include <ext/pb_ds/assoc_container.hpp>
10 //#include <ext/pb_ds/tree_policy.hpp>
11 #define LL long long
12 
13 using namespace std;
14 //using namespace __gnu_pbds;
15 
16 int dp[1<<20];
17 
18 int attack[20][20],health[20];
19 
20 int n;
21 
22 int check(int j,int i)
23 {
24     int a = 1;
25     a = max(a,attack[j][i]);
26     return (health[i]/a) + (health[i]%a?1:0);
27 }
28 
29 int dfs(int statu)
30 {
31     if(dp[statu] != -1)
32         return dp[statu];
33     dp[statu] = 0x3f3f3f3f;
34     if(statu == 0)
35         return dp[statu] = 0;
36     for(int i = 1; i <= n; i++)
37     {
38         if( ((statu>>(i-1))&1) == 0 )
39             continue;
40         dp[statu] = min(dp[statu],dfs( (statu^(1<<(i-1))))+health[i]/1);
41         for(int j = 1; j <= n; j++)
42         {
43             if(i == j) continue;
44 
45             if( ((statu>>(j-1))&1) == 0)
46             {
47                 dp[statu] = min(dp[statu],dfs( (statu^(1<<(i-1)) )) + check(j,i) );
48             }
49         }
50 
51     }
52 
53     return dp[statu];
54 }
55 
56 void solve()
57 {
58     memset(dp,-1,sizeof(dp));
59 
60     scanf("%d",&n);
61     for(int i = 1; i <= n; i++)
62         scanf("%d",&health[i]);
63     for(int i = 1; i <= n; i++)
64         for(int j = 1; j <= n; j++)
65             scanf("%1d",&attack[i][j]);
66 
67     int ans =  dfs( (1<<n)-1);
68 
69     printf("%d
",ans);
70 }
71 
72 
73 int main(void)
74 {
75     int t,cnt = 0;
76     scanf("%d",&t);
77     while(t--)
78     {
79         printf("Case %d: ",++cnt);
80         solve();
81     }
82     return 0;
83 }