- dp[S]表示已经消灭目标集合为S的最少射击数
- dp[0]=0
- dp[S]=min( dp[S'] + min( health[i] , health[i]/demage[j][i] ) ) 其中S-S'={i}，j∈S'
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define INF (1<<29) 6 int d[1<<15],a[15][15],b[15]; 7 int main(){ 8 int t,n; 9 scanf("%d",&t); 10 for(int cse=1; cse<=t; ++cse){ 11 scanf("%d",&n); 12 for(int i=0; i<n; ++i) scanf("%d",b+i); 13 for(int i=0; i<n; ++i){ 14 for(int j=0; j<n; ++j) scanf("%1d",&a[i][j]); 15 } 16 for(int i=1; i<(1<<n); ++i) d[i]=INF; 17 for(int i=1; i<(1<<n); ++i){ 18 for(int j=0; j<n; ++j){ 19 if(((i>>j)&1)==0) continue; 20 int time=b[j]; 21 for(int k=0; k<n; ++k){ 22 if(j==k || ((i>>k)&1)==0 || a[k][j]==0) continue; 23 time=min(time,b[j]/a[k][j]+(b[j]%a[k][j]!=0)); 24 } 25 d[i]=min(d[i],d[i^(1<<j)]+time); 26 } 27 28 } 29 printf("Case %d: %d ",cse,d[(1<<n)-1]); 30 } 31 return 0; 32 }