問題
http://community.topcoder.com/stat?c=problem_statement&pm=12314&rd=15183
解き方
maxAcceptedの数は15個までなので、各問題についてMとLすべての分け方を試すことが
できる。
各分け方について、貪欲に風船を割り当てていけば最適解が求まる。
コード
class ICPCBalloons {
public: int minRepaintings(vector<int> balloonCount, string balloonSize, vector<int> maxAccepted) {
int n=maxAccepted.size();
vector<int> m,l;
int allm=0,alll=0;
FORE(i,0,balloonCount.size()){
if(balloonSize[i]=='M'){
m.push_back(balloonCount[i]);
allm+=balloonCount[i];
}else{
l.push_back(balloonCount[i]);
alll+=balloonCount[i];
}
}
sort(m.rbegin(),m.rend());
sort(l.rbegin(),l.rend());
int ret=1e+9;
for(int mask=0;mask<(1<<n);mask++){
vector<int> cm,cl;
int cntm=0,cntl=0;
FORE(i,0,n){
if(mask&(1<<i)){
cm.push_back(maxAccepted[i]);
cntm+=maxAccepted[i];
}else{
cl.push_back(maxAccepted[i]);
cntl+=maxAccepted[i];
}
}
if(allm<cntm || alll<cntl)continue;
int cost=0;
sort(cm.rbegin(),cm.rend());
sort(cl.rbegin(),cl.rend());
FORE(i,0,cm.size()){
int cur= i>=m.size() ? 0 : m[i];
cost+=cm[i]-min(cm[i],cur);
}
FORE(i,0,cl.size()){
int cur= i>=l.size() ? 0 : l[i];
cost+=cl[i]-min(cl[i],cur);
}
ret=min(ret,cost);
}
return ret==1e+9 ? -1 : ret;
}
};
public: int minRepaintings(vector<int> balloonCount, string balloonSize, vector<int> maxAccepted) {
int n=maxAccepted.size();
vector<int> m,l;
int allm=0,alll=0;
FORE(i,0,balloonCount.size()){
if(balloonSize[i]=='M'){
m.push_back(balloonCount[i]);
allm+=balloonCount[i];
}else{
l.push_back(balloonCount[i]);
alll+=balloonCount[i];
}
}
sort(m.rbegin(),m.rend());
sort(l.rbegin(),l.rend());
int ret=1e+9;
for(int mask=0;mask<(1<<n);mask++){
vector<int> cm,cl;
int cntm=0,cntl=0;
FORE(i,0,n){
if(mask&(1<<i)){
cm.push_back(maxAccepted[i]);
cntm+=maxAccepted[i];
}else{
cl.push_back(maxAccepted[i]);
cntl+=maxAccepted[i];
}
}
if(allm<cntm || alll<cntl)continue;
int cost=0;
sort(cm.rbegin(),cm.rend());
sort(cl.rbegin(),cl.rend());
FORE(i,0,cm.size()){
int cur= i>=m.size() ? 0 : m[i];
cost+=cm[i]-min(cm[i],cur);
}
FORE(i,0,cl.size()){
int cur= i>=l.size() ? 0 : l[i];
cost+=cl[i]-min(cl[i],cur);
}
ret=min(ret,cost);
}
return ret==1e+9 ? -1 : ret;
}
};