codeforces 768 D. Jon and Orbs（概率dp）

题目链接：http://codeforces.com/contest/768/problem/D

题意：一共有k种球，要得到k种不同的球至少一个，q个提问每次提问给出一个数pi，问概率大小大于等于pi

至少要几天，每天都能等概率的出一种球。

题解：一道简单的概率dp，很明显要设dp[i][j]表示第i天得到j种球的概率，转移方程如下。

dp[i][j] = dp[i - 1][j - 1] * (1.0 * (k - j + 1) / k) + dp[i - 1][j] * (1.0 * j / k);

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

using namespace std;

const int M = 3e3 + 10;

double dp[10010][M];

int main() {

    int k , q;

    cin >> k >> q;

    memset(dp , 0 , sizeof(dp));

    dp[1][1] = 1.0;

    for(int i = 2 ; i <= 10000 ; i++) {

        for(int j = 1 ; j <= k && j <= i ; j++) {

            dp[i][j] = dp[i - 1][j - 1] * (1.0 * (k - j + 1) / k) + dp[i - 1][j] * (1.0 * j / k);

        }

    }

    while(q--) {

        int p;

        cin >> p;

        for(int i = 1 ; i <= 10000 ; i++) {

            if(dp[i][k] >= 1.0 * p / 2000) {

                cout << i << endl;

                break;

            }

        }

    }

    return 0;

}

巴特西

codeforces 768 D. Jon and Orbs（概率dp）

最新文章

热门文章