题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1037
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 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 " , ++ans , dp[(1 << n) - 1]); 36 } 37 return 0; 38 }
题解：简单的状压dp存一下被kill的人的状态就行。