程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LightOJ1317---Throwing Balls into the Baskets (概率dp)

LightOJ1317---Throwing Balls into the Baskets (概率dp)

編輯：C++入門知識

LightOJ1317---Throwing Balls into the Baskets (概率dp)

You probably have played the game “Throwing Balls into the Basket”. It is a simple game. You have to throw a ball into a basket from a certain distance. One day we (the AIUB ACMMER) were playing the game. But it was slightly different from the main game. In our game we were N people trying to throw balls into M identical Baskets. At each turn we all were selecting a basket and trying to throw a ball into it. After the game we saw exactly S balls were successful. Now you will be given the value of N and M. For each player probability of throwing a ball into any basket successfully is P. Assume that there are infinitely many balls and the probability of choosing a basket by any player is 1/M. If multiple people choose a common basket and throw their ball, you can assume that their balls will not conflict, and the probability remains same for getting inside a basket. You have to find the expected number of balls entered into the baskets after K turns.
Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing three integers N (1 ≤ N ≤ 16), M (1 ≤ M ≤ 100) and K (0 ≤ K ≤ 100) and a real number P (0 ≤ P ≤ 1). P contains at most three places after the decimal point.
Output

For each case, print the case number and the expected number of balls. Errors less than 10-6 will be ignored.
Sample Input

Output for Sample Input

1 1 1 0.5

1 1 2 0.5

Case 1: 0.5

Case 2: 1.000000

Problem Setter: Muhammad Rifayat Samee
Special Thanks: Jane Alam Jan

首先我們要知道每一次扔的時候,0個人扔進的概率,1個人扔進的概率….
由於最後不關心M個籃子裡球的具體情況,所以M其實沒有什麼用
只要區分扔不扔進去,至於扔到哪個籃子不管
dp[i][j]表示到第i輪,籃子裡有j個球的概率
最後答案就是Σi?dp[k][i]

/*************************************************************************
    > File Name: L.cpp
    > Author: ALex
    > Mail: [email protected] 
    > Created Time: 2015年05月17日 星期日 16時05分37秒
 ************************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 

using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair  PLL;

double dp[110][1700]; //ith turns, p of j balls 
double Pa[20];
int C[20][20];

void init() {
    C[0][0] = 1;
    for (int i = 1; i <= 16; ++i) {
        C[i][0] = 1;
        C[i][1] = i;
        for (int j = 2; j < i; ++j) {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
        C[i][i] = 1;
    }
}

double Pow(double a, int b) {
    double ans = 1;
    for (int i = 1; i <= b; ++i) {
        ans *= a;
    }
    return ans;
}

int main() {
    init();
    int t;
    int icase = 1;
    scanf("%d", &t);
    while (t--) {
        int n, m, k;
        double p;
        scanf("%d%d%d%lf", &n, &m, &k, &p);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0; i <= n; ++i) {
            Pa[i] = C[n][i] * Pow(p, i) * Pow((1 - p), n - i);
        }
        for (int i = 1; i <= k; ++i) {
            for (int j = 0; j <= (i - 1) * n; ++j) {
                for (int l = 0; l <= n; ++l) {
                    if (j + l <= i * n) {
                        dp[i][j + l] += dp[i - 1][j] * Pa[l];
                    }
                }
            }
        }
        double E = 0;
        for (int i = 0; i <= k * n; ++i) {
            E += dp[k][i] * i;
        }
        printf("Case %d: %.12f\n", icase++, E);
    }
    return 0;
}