問題
http://community.topcoder.com/stat?c=problem_statement&pm=13540&rd=16085
・バスが複数あり、各バスごとに１周にかかる時間と、そのバスが選ばれる確率が与えられる。
・スタート時にひとつのバスが与えられた確率で選ばれ、そのバスが戻ってきたときに
また、そのバスを含むすべてのバスからひとつ選ばれ出発する。
・あなたが到着する時間が与えられるとき、待ち時間の期待値を求める。
解き方
期待値を求めるのでｄｐが使えそう。
dp[現在の時刻]と定義する。
各dp[i]について、すべてのバスjに対してdp[i+time[j]]を更新する。
このとき、i+time[j]が自分が到着する時間よりも大きければその待ち時間を
答えの期待値に加えていけば良い。
コード
double dp[100001];
class WaitingForBus {
public: double whenWillBusArrive(vector<int> time, vector<int> prob, int s) {
if(s==0)return 0.0;
int n=time.size();
double ret=0.0;
memset(dp,0,sizeof(dp));
dp[0]=1.0;
for(int i=0;i<s;i++){
FORE(j,0,n){
if(s<=i+time[j])ret+=(i+time[j]-s)*dp[i]*prob[j]/100.0;
else dp[i+time[j]]+=dp[i]*prob[j]/100.0;
}
}
return ret;
}
};
class WaitingForBus {
public: double whenWillBusArrive(vector<int> time, vector<int> prob, int s) {
if(s==0)return 0.0;
int n=time.size();
double ret=0.0;
memset(dp,0,sizeof(dp));
dp[0]=1.0;
for(int i=0;i<s;i++){
FORE(j,0,n){
if(s<=i+time[j])ret+=(i+time[j]-s)*dp[i]*prob[j]/100.0;
else dp[i+time[j]]+=dp[i]*prob[j]/100.0;
}
}
return ret;
}
};