题目大意：
有个特工要执行任务，他会遭遇到最多15个目标，特工必须把他们全部杀死。当他杀死一个目标后他可以使用目标的武器来杀死其他人。因此他必须有一个杀人的顺序，使得他开枪的次数最小。
现在给你一个表，代表每种武器对每个目标可以造成多少伤害。并且你知道每个目标的血量。当这个目标的血量小于等于0的时候说明这个目标被杀死了。最初的时候这个特工只有一个枪，这个枪可以对一个目标造成1点伤害。
题目分析： 先把每个状态下最敌人造成的伤害预处理出来，然后再进行一次记忆化搜索。
===========================================================================================
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<vector> 8 #include<map> 9 using namespace std; 10 typedef long long LL; 11 const int INF = 1e9+7; 12 const int MAXN = 60055; 13 int dp[MAXN], Att[MAXN][20]; 14 int HP[20], M[20][20], n, Lim; 15 int DFS(int sta) 16 { 17 if(dp[sta] != -1) 18 return dp[sta]; 19 if(sta == 0) 20 return dp[0] = 0; 21 dp[sta] = INF; 22 for(int i=0; i<n; i++) 23 { 24 if( sta&(1<<i) ) 25 { 26 int newSta = sta - (1<<i); 27 int k = (HP[i] + Att[newSta][i] - 1)/Att[newSta][i]; 28 dp[sta] = min(dp[sta], k + DFS(newSta)); 29 } 30 } 31 return dp[sta]; 32 } 33 34 int main() 35 { 36 int T, cas = 1; 37 char str[50]; 38 scanf("%d", &T); 39 while(T --) 40 { 41 scanf("%d", &n); 42 memset(dp, -1, sizeof(dp)); 43 memset(Att, 0, sizeof(Att)); 44 for(int i=0; i<n; i++) 45 { 46 scanf("%d", &HP[i]); 47 Att[0][i] = 1; 48 } 49 for(int i=0; i<n; i++) 50 { 51 scanf("%s", str); 52 for(int j=0; j<n; j++) 53 M[i][j] = str[j] - '0'; 54 } 55 Lim = (1<<n) - 1; 56 /**把所有的攻击力状态预处理出来*/ 57 for(int i=0; i<=Lim; i++)///30000 58 for(int j=0; j<n; j++)///15 59 { 60 if( (i&(1<<j)) ) 61 { 62 int newSta = i - (1<<j); 63 for(int k=0; k<n; k++) 64 Att[i][k] = max(Att[newSta][k], M[j][k]); 65 } 66 } 67 printf("Case %d: %d ",cas ++, DFS(Lim) ); 68 } 69 return 0; 70 }