mayoko’s diary

プロコンとかいろいろ。

SRM 642 div1 easy:WaitingForBus

これは簡単。

問題:TopCoder Statistics - Problem Statement

解法:t分後にバスが来る確率を動的計画法で求める。s分前にバスが来た場合はまだジョセフさんが待つ時間が確定していないので動的計画法を続ける必要があるが,s分以降バスが来てからはジョセフさんはバスに乗ってしまうのでそれ以降は考える必要がない。
以下ソースコード

const int MAXT = 100100;
double dp[2*MAXT];

class WaitingForBus {
public:
    double whenWillBusArrive(vector <int> time, vector <int> prob, int s) {
        int n = prob.size();
        vector<double> p(n);
        for (int i = 0; i < n; i++) p[i] = prob[i]/100.;
        for (int i = 0; i < 2*MAXT; i++) dp[i] = -1;
        dp[0] = 1;
        for (int i = 0; i < s; i++) {
            if (dp[i] < 0) continue;
            for (int j = 0; j < n; j++) {
                if (dp[i+time[j]] < 0) dp[i+time[j]] = 0;
                dp[i+time[j]] += dp[i]*p[j];
            }
        }
        double ret = 0;
        for (int i = s; i < 2*MAXT; i++) {
            if (dp[i] >= 0) ret += (i-s)*dp[i];
        }
        return ret;
    }
};