問題
http://topcoder.bgcoder.com/print.php?id=1855
電気で電源が入る植物があり、電源はＯＮになっている他の植物から共有される。
各植物同士のＯＮにする電源量はあらかじめわかっている。
また、現在ＯＮになっている植物もわかっている。
このとき、numPlants本の植物をＯＮにするのに必要な最小の電源量を求める。
解き方
ｄｐで解く。
状態として、現在ＯＮになっている植物を持っていればよい。
植物はすべてで１６本なので計算量も間に合う。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PowerPlants {
public:
int f(char ch){
if('0'<=ch && ch<='9')return (int)(ch-'0');
return (int)(ch-'A')+10;
}
int minCost(vector<string> connectionCost, string plantList, int numPlants) {
int p[16][16];
int n=connectionCost.size();
int ret=1e+9;
FORE(i,0,n)FORE(j,0,n)p[i][j]=f(connectionCost[i][j]);
int dp[1<<16],s=0;
FORE(i,0,n)if(plantList[i]=='Y')s|=(1<<i);
FORE(i,0,1<<16)dp[i]=1e+9;
dp[s]=0;
FORE(i,1,1<<n){
FORE(j,0,n)if(i&(1<<j))FORE(k,0,n){
dp[i|(1<<k)]=min(dp[i|(1<<k)],dp[i]+p[j][k]);
}
if(__builtin_popcount(i)>=numPlants)ret=min(ret,dp[i]);
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PowerPlants {
public:
int f(char ch){
if('0'<=ch && ch<='9')return (int)(ch-'0');
return (int)(ch-'A')+10;
}
int minCost(vector<string> connectionCost, string plantList, int numPlants) {
int p[16][16];
int n=connectionCost.size();
int ret=1e+9;
FORE(i,0,n)FORE(j,0,n)p[i][j]=f(connectionCost[i][j]);
int dp[1<<16],s=0;
FORE(i,0,n)if(plantList[i]=='Y')s|=(1<<i);
FORE(i,0,1<<16)dp[i]=1e+9;
dp[s]=0;
FORE(i,1,1<<n){
FORE(j,0,n)if(i&(1<<j))FORE(k,0,n){
dp[i|(1<<k)]=min(dp[i|(1<<k)],dp[i]+p[j][k]);
}
if(__builtin_popcount(i)>=numPlants)ret=min(ret,dp[i]);
}
return ret;
}
};