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) -  );
        }
 }