SRM 642 DIV1 Easy - WaitingForBus x

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13540&rd=16085

・バスが複数あり、各バスごとに1周にかかる時間と、そのバスが選ばれる確率が与えられる。
・スタート時にひとつのバスが与えられた確率で選ばれ、そのバスが戻ってきたときに
また、そのバスを含むすべてのバスからひとつ選ばれ出発する。

・あなたが到着する時間が与えられるとき、待ち時間の期待値を求める。

解き方


期待値を求めるのでdpが使えそう。

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;
}

};

Share this

Related Posts

Previous
Next Post »