TopCoder SRM 364 Div1 Medium PowerPlants
問題
n個の発電所がある。
そのうち、最初から起動しているものはplantListによって与えられる。
すでに起動している発電所iを使って発電所jを起動させるコストconnectionCost[i][j]が与えられる。
合計でnumPlants個以上の発電所を起動させるのに必要なコストの総和の最小値を求めよ。
制約条件
connectionCost[i][j]≦36
n≦16
ソースコード
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; } };