Carnival Coins

問題

コインが$n$枚与えられる。 適当に$i$枚コインをまとめて投げてよい。投げたコインは消費される。 コインは一様な確率$p$で表がでる。 コインを投げて表が$k$枚以上でるたびに、景品が$1$つ貰える。 $n$枚を最適に投げたとき、貰える景品の数の期待値を答えよ。

解法

普通にdp。

まず$i$個コインを投げたときに$k$個以上表になる確率をdpして、これを元に$n$個コインを使ったときに貰える景品の数の期待値をdp。

実装

#include <iostream>
#include <vector>
#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
void solve() {
    int n, k; double p; cin >> n >> k >> p;
    vector<double> q(n+1); {
        vector<double> cur(k+1), prv;
        cur[0] = 1;
        repeat (i,n) {
            prv = cur;
            cur[0] = prv[0]*(1-p);
            repeat_from (j,1,k) cur[j] = prv[j]*(1-p) + prv[j-1]*p;
            cur[k] = prv[k] + prv[k-1]*p;
            q[i+1] = cur[k];
        }
    }
    vector<double> dp(n+1);
    repeat (i,n+1) {
        repeat (j,i+1) {
            dp[i] = max(dp[i], dp[i-j] + q[j]);
        }
    }
    printf("%.12lf\n", dp[n]);
}
int main() {
    int testcases; cin >> testcases;
    repeat (testcase, testcases) {
        cout << "Case #" << testcase+1 << ": ";
        solve();
    }
    return 0;
}