全体公開 > 合同練習会 > 20130323 > H 良い連立政権

問題の概要

安定した連立政権を作りたい.
各党が獲得した議席数(足すと150)と, 連立政権からの離脱率が与えられる.
76議席以上になる組み合わせで, 一党も連立政権から離脱しない確率が最も高くなるようにした場合, その確率を求めよ.

実装の方針, 注意点

...

連立政権にある党 が加わると, 議席数は 増え, 一党も連立政権から離脱しない確率は 倍される.
議席数でDPする.
dp[何番目の党まで考慮したか][合計の議席数]=最も高い確率 なる配列を用いた.

ソースコード

...

bool solve(){
    int n; cin >> n;
    vector<vector<double> > dp(n+1, vector<double>(160, 0));
    dp[0][0] = 1;
    rep(i, n){
        int s, p; cin >> s >> p;
        dp[i+1] = dp[i];
        rep(t, 160) if(t+s < 160){
            maxeq(dp[i+1][t+s], dp[i][t] * (p / 100.0));
        }
    }
    double res = 0;
    for(int t = 76; t < 160; ++t) maxeq(res, dp[n][t]);
    cout << res*100 << endl;
    return true;
}
 

編集

---