题目链接：

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inf 0X3f3f3f3f 5 using namespace std; 6 int dp[1 << 16] , hp[20]; 7 char dam[20][20]; 8 int main() { 9     int t , ans = 0;10     scanf("%d" , &t);11     while(t--) {12         int n;13         scanf("%d" , &n);14         for(int i = 0 ; i < n ; i++) scanf("%d" , &hp[i]);15         for(int i = 0 ; i < n ; i++) {16             scanf("%s" , dam[i]);17         }18         memset(dp , inf , sizeof(dp));19         dp[0] = 0;20         for(int i = 0 ; i < (1 << n) ; i++) {21             for(int j = 0 ; j < n ; j++) {22                 if(i & (1 << j)) continue;23                 else {24                     dp[i | (1 << j)] = min(dp[i | (1 << j)] , dp[i] + hp[j]);25                     for(int k = 0 ; k < n ; k++) {26                         if(i & (1 << k)) {27                             int tm = 1;28                             if(dam[k][j] - '0') tm = dam[k][j] - '0';29                             dp[i | (1 << j)] = min(dp[i | (1 << j)] , dp[i] + hp[j] / tm + (hp[j] % tm == 0 ? 0 : 1));30                         }31                     }32                 }33             }34         }35         printf("Case %d: %d\n" , ++ans , dp[(1 << n) - 1]);36     }37     return 0;38 }
       
      
     

 

题解：简单的状压dp存一下被kill的人的状态就行。