srm 181 div1 1000（狀壓dp）

題意：

克洛人。。打敗n個Boss通關。每個Boss掉一把裝備，每把裝備對n個Boss有不同傷害值。初始有一把對所有Boss傷害值都為1的槍。

n no more than 15，求最少攻擊次數

思路：

用最多15個bit來表示現在擁有的武器。然後可以用記憶化搜尋解決。

轉移的時候，先枚舉被打敗的boss，再枚舉費用，即使用哪把武器攻擊次數最少。

int dp[], shots[][], n;

class KiloManX
{
        public:
    int go(int x) {
        if (dp[x] != -) return dp[x];
        int &ret = dp[x];
        ret = inf;
        rep(i, , n-) if (<<i & x) {
            int cost = shots[n][i]; // default weapon
            rep(j, , n-) if (i != j && (<<j & x)) // choose minimum cost
                cost = min(cost, shots[j][i]);
            ret = min (ret, cost + go (x ^ (<<i)));
        }
        return ret;
    }

        int leastShots(vector <string> damageChart, vector <int> bossHealth)
        {
        n = damageChart.size();
        rep(i, , n-) shots[n][i] = bossHealth[i];
        rep(i, , n-) rep(j, , n-) {
            if (i == j || damageChart[i][j] == '0') shots[i][j] = inf;
            else shots[i][j] = (bossHealth[j] + damageChart[i][j] - '1') / (damageChart[i][j] - '0');
        }
        memset(dp, -, sizeof(dp));
        dp[] = ;
        return go( (<<n) -  );
        }
 }