Lightoj 1037 - Agent 47

http://lightoj.com/volume_showproblem.php?problem=1037

1. #include <bits/stdc++.h>
2. using namespace std;
3. inline int _Int(){ int x; scanf( "%d", &x ); return x; }
4. int n;
5. int Health[15];
6. char Destroy[15][15];
7. int dp[ (1<<15)+3 ];
8. int bitmask_dp( int mask ){
9.     if( mask == ( 1<<n )-1 )return 0;
10.     if( dp[mask] != -1 )return dp[mask];
11.     dp[mask] = INT_MAX;
12.     for( int i = 0; i < n; i++ ){
13.         if( !(mask&(1<<i)) ){
14.             for(int j = 0; j < n; j++){
15.                 if( (mask&(1<<j)) ){
16.                     int x = Destroy[j][i]-'0';
17.                     if(!x)continue;
18.                     int y = Health[i]/x;
19.                     if(Health[i]%x)y++;
20.                     dp[mask] = min( dp[mask], y+bitmask_dp( ( mask|(1<<i) ) ) );
21.                 }
22.             }
23.             dp[mask] = min( dp[mask], Health[i]+bitmask_dp( ( mask|(1<<i) ) ) );
24.         }
25.     }
26.     return dp[mask];
27. }
28. int main(){
29.     int t = _Int(), cs = 0;
30.     while(t--){
31.         n = _Int();
32.         memset(dp, -1, sizeof(dp));
33.         for( int i = 0; i < n; i++ ) Health[i] = _Int();
34.         for( int i = 0; i < n; i++ ) scanf( "%s", Destroy[i] );
35.         int mn = INT_MAX;
36.         for( int i = 0; i < n; i++ ){
37.             mn = min( mn, Health[i] + bitmask_dp( (1<<i) ) );
38.         }
39.         printf( "Case %d: %d\n", ++cs,  mn );
40.     }
41.     return 0;
42. }