問題
http://community.topcoder.com/stat?c=problem_statement&pm=11508&rd=14540
売り物である剣を任意の数持っており、複数の顧客が訪れる。
各顧客について、"時間、買う値段、来る確率"で表わされる情報が複数個与えられる。
ただし、一人の顧客について１つの剣しか売ることができない。
このとき、得られる収益の最大値を求める。
解き方
ぱっと見てｄｐで解けそう。
どうｄｐを適用するかが問題。
問題文から読みとると時系列の処理が必要なので、時間ごとに処理を行っていく。
次に、各顧客について訪れたか訪れていないかの情報を保存しようとすると２＾２４で発散するため難しい。
ただし、どの顧客を選ぶかの情報であれば２４Ｃ１２のため２＊１０＾６程度になる。
さらに、一度しか訪れない顧客は２度現れないことから情報を保存しなくてもよいので計算量が削減できる。よって、２度以上現れる顧客のみINDEXを順につけてあげる。
上記より、「時間、現在の剣の在庫、すでに選んだ顧客の情報」を元にｄｐを回せばよい。
訪れる顧客は最大で２４人、うち複数回訪れる顧客は最大１２人のため、２＾１２分のビットマスクで足りる。
ｄｐでは、
①その時間に既に現れた顧客であれば時間のみ進め、
②まだ現れていない顧客でありその時間にも現れなければ、現れない確立をかけて進め、
③現れた場合であれば、その顧客に売ったときもしくは売らないときの最大の値をとってあげればよい。
コード
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()
int N[24],M[24];
double P[24],dp[26][24][5000];
class NewItemShop {
public:
double f(int swords,int hour,int mask){
if(swords==0||hour==24)return 0.0;
if(dp[swords][hour][mask]>0)return dp[swords][hour][mask];
if(N[hour]==-1)return dp[swords][hour][mask]=f(swords,hour+1,mask);
int cmask= M[hour]<100 ? (1<<M[hour]) : 0;
if((cmask&mask)>0)return dp[swords][hour][mask]=f(swords,hour+1,mask);
dp[swords][hour][mask]=(1.0-P[hour])*f(swords,hour+1,mask);
double ret=max(N[hour]+f(swords-1,hour+1,mask|cmask),f(swords,hour+1,mask|cmask));
dp[swords][hour][mask]+=P[hour]*ret;
return dp[swords][hour][mask];
}
double getMaximum(int swords, vector<string> customers) {
memset(N,-1,sizeof(N));
memset(P,0,sizeof(P));
memset(M,0,sizeof(M));
memset(dp,0,sizeof(dp));
int multi=0;
FORE(i,0,(int)customers.size()){
stringstream out(customers[i]);
string str;
int index= customers[i].size()>9 ? multi++ : 1000;
double prob=1.0;
while(out>>str){
FORE(i,0,(int)str.size())if(str[i]==',')str[i]=' ';
int t[3];
stringstream out2(str);
out2>>t[0]>>t[1]>>t[2];
N[t[0]]=t[1];
double curprob=(double)t[2]/100.0;
P[t[0]]=curprob/prob;
prob-=curprob;
M[t[0]]=index;
}
}
return f(swords,0,0);
}
};
#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()
int N[24],M[24];
double P[24],dp[26][24][5000];
class NewItemShop {
public:
double f(int swords,int hour,int mask){
if(swords==0||hour==24)return 0.0;
if(dp[swords][hour][mask]>0)return dp[swords][hour][mask];
if(N[hour]==-1)return dp[swords][hour][mask]=f(swords,hour+1,mask);
int cmask= M[hour]<100 ? (1<<M[hour]) : 0;
if((cmask&mask)>0)return dp[swords][hour][mask]=f(swords,hour+1,mask);
dp[swords][hour][mask]=(1.0-P[hour])*f(swords,hour+1,mask);
double ret=max(N[hour]+f(swords-1,hour+1,mask|cmask),f(swords,hour+1,mask|cmask));
dp[swords][hour][mask]+=P[hour]*ret;
return dp[swords][hour][mask];
}
double getMaximum(int swords, vector<string> customers) {
memset(N,-1,sizeof(N));
memset(P,0,sizeof(P));
memset(M,0,sizeof(M));
memset(dp,0,sizeof(dp));
int multi=0;
FORE(i,0,(int)customers.size()){
stringstream out(customers[i]);
string str;
int index= customers[i].size()>9 ? multi++ : 1000;
double prob=1.0;
while(out>>str){
FORE(i,0,(int)str.size())if(str[i]==',')str[i]=' ';
int t[3];
stringstream out2(str);
out2>>t[0]>>t[1]>>t[2];
N[t[0]]=t[1];
double curprob=(double)t[2]/100.0;
P[t[0]]=curprob/prob;
prob-=curprob;
M[t[0]]=index;
}
}
return f(swords,0,0);
}
};