TopCoder SRM 364 Div1 Medium PowerPlants

問題

n個の発電所がある。
そのうち、最初から起動しているものはplantListによって与えられる。
すでに起動している発電所iを使って発電所jを起動させるコストconnectionCost[i][j]が与えられる。


合計でnumPlants個以上の発電所を起動させるのに必要なコストの総和の最小値を求めよ。

制約条件

connectionCost[i][j]≦36
n≦16

方針

ビットDP.
dp[i]を、ビットiで表される発電所を起動するのにかかるコストの最小値とする。
すると、それを使って起動できる発電所のコストからテーブルが更新できる。

ソースコード

int cost[16][16],dp[1<<16];

class PowerPlants {
  public:
  int minCost(vector <string> connectionCost, string plantList, int numPlants) {
    int n=connectionCost.size();
    rep(i,n)rep(j,n){
      if(isdigit(connectionCost[i][j]))cost[i][j]=connectionCost[i][j]-'0';
      else cost[i][j]=connectionCost[i][j]-'A'+10;
    }
    
    rep(i,1<<n)dp[i]=inf;
    int s=0, ans=inf;
    
    rep(i,n)if(plantList[i]=='Y')s|=1<<i;
    dp[s]=0;
    rep(i,1<<n){
      rep(j,n)if(i&1<<j)rep(k,n)
        dp[i|1<<k]=min(dp[i|1<<k],dp[i]+cost[j][k]);
      if(__builtin_popcount(i)>=numPlants)ans=min(ans,dp[i]);
    }
    return ans;
  }
};