uva 11427 - Expect the Expected(概率)

uva 11427 - Expect the Expected(概率)

題目鏈接：uva 11427 - Expect the Expected

題目大意：你每天晚上都會玩紙牌，每天固定最多玩n盤，每盤勝利的概率為p，你是一個固執的人，每天一定要保證勝局的比例大於p才會結束游戲，若n局後仍沒有，就會不開心，然後以後再也不完牌，問說你最多會玩多少個晚上。

解題思路：當j/i ≤ p時有dp(i-1,j) (1-p) + dp(i-1, j-1) p,其他dp(i,j) = 0.Q=∑d(n,i)
列出數學期望公式：
EX=Q+2Q(1?Q)+3Q(1?Q)2+…
s=EXQ=1+2(1?Q)+3(1?Q)2+…
(1?Q)?s=(1?Q)+2(1?Q)2+3(1?Q)3+…
EX=Qs=1+(1?Q)+(1?Q)2+(1?Q)3…
為等比數列，根據等比數列求和公式，n趨近無窮大是為1/Q

#include 
#include 
#include 

using namespace std;
const int maxn = 105;

double dp[maxn][maxn];

int main () {
    int cas;
    scanf("%d", &cas);
    for (int kcas = 1; kcas <= cas; kcas++) {
        int a, b, n;
        scanf("%d/%d%d", &a, &b, &n);
        double p = (double)a / b;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        dp[0][1] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j * b <= a * i; j++) {
                dp[i][j] = dp[i-1][j] * (1-p);
                if (j)
                    dp[i][j] += dp[i-1][j-1] * p;
            }
        }

        double q = 0;
        for (int i = 0; i * b <= a * n; i++)
            q += dp[n][i];
        printf("Case #%d: %d\n", kcas, (int)(1/q));
    }
    return 0;
}