SRM 515 Div1 Medium NewItemShop

最近薬変えたらめちゃくちゃ体調悪くて練習どころじゃないorz
まあぼちぼち体調整えながらやっていこう。

本番で参加しなかったのでエアSRM.
状態数減らす工夫が思い浮かばなかった（TLE解法は書けた)。

問題

swords本の剣を売る店を出す。
店には客が何人か来る。客のそれぞれの情報はcustomer[i]によって与えられる。

customer[i]は以下の形式である。
"T1,C1,P1 T2,C2,P2 ... Tn,Cn,Pn"
ここでTj,Cj,Pjはこの客が時間Tjに来る確率がPjで、その時の剣の買値がCjであるという意味である。
それぞれの客は最大で1度しかこの店に来ない。
すなわち、客が店に1度も来ない確率は100-(P1+P2+...+Pn)%である。

店主は来た客に対して剣を売るか売らないかを選択することができる。
店主が最善の戦略を取るとき、店の利益の期待値の最大値を求めよ。

ただし、客が同じ時間に同時に来ることはないものとする。

制約条件

1≦swords≦24
T＜24
C,P＜100
customerの要素≦24

方針

すぐに思い浮かぶのは次のようなDP.
今残っている剣と、まだ訪れてない客のビット、現在の時間をキーとして、
その時の利益の期待値の最大値を保存しておくメモ化探索。

ところがこれだと状態数が24*2^24*24になってケースによっては爆発する。
そこで、次のような工夫をする。
1度しか来ない客はビットとして持つ意味が無いので、2度以上訪れる客のみについてbitを持つ。

すると状態数は24*24*2^12以下になるので間に合う。

ソースコード

int n;
map<pi,double> dp;
pair<pair<int,pi>,pi> ord[25]; //time,id,bit,cost,prob

double rec(int c,int swords,int mask){
	if(dp.count(mp(swords*25+c,mask)))return dp[mp(swords*25+c,mask)];
	double &ret=dp[mp(swords*25+c,mask)];
	
	if(c==n||swords==0)return ret=0;
	if(mask&ord[c].first.second.second)return ret=rec(c+1,swords,mask);
	
	int nmask=mask|ord[c].first.second.second;
	double e=0,p=ord[c].second.second,q=100;
	rep(i,c)if(ord[i].first.second.first==ord[c].first.second.first){
		q-=ord[i].second.second;
	}
	p/=q; //条件付き確率を求めてやらねばならぬことに注意。
	
	e=ord[c].second.first+rec(c+1,swords-1,nmask);
	e=max(e,rec(c+1,swords,nmask));
	ret=e*p + rec(c+1,swords,mask)*(1-p);
	
	return ret;
}

class NewItemShop {
public:
  double getMaximum(int swords, vector <string> cus) {
  	
  	dp.clear();
  	n=0;
  	int m=0,bit=0;
  	rep(i,cus.size()){
  		stringstream ss(cus[i]);
  		string s;
  		if(cus[i].find(" ")!=cus[i].npos)bit=1<<m++; else bit=0;
  		while(ss>>s){
  			int t,c,p; sscanf(s.c_str(),"%d,%d,%d",&t,&c,&p);
	  		ord[n++]=mp(mp(t,mp(i,bit)),mp(c,p));
  		}
  	}
  	sort(ord,ord+n);
  	return rec(0,swords,0);
  }
};