TCO11 Qual1 Medium(500) FoxListeningToMusic

TopCoder

FoxListeningToMusic

時刻ごとに曲が終わる確率を動的計画法で求め、t秒後にT-tより長い曲が選ばれる確率を足し合わせる。

#include <vector>
using namespace std;

class FoxListeningToMusic{public:
vector <double> getProbabilities( vector <int> length, int T )
{
    int n = (int)length.size();

    vector<double> S(T+1);
    S[0] = 1;

    vector<double> ans(n);

    for ( int i=0; i<=T; i++ )
        for ( int j=0; j<n; j++ )
            if ( i+length[j] <= T )
                S[i+length[j]] += S[i]/n;
            else
                ans[j] += S[i]/n;

    return ans;
}};