Coins I

题目描述

Alice and Bob are playing a simple game. They line up a row of n identical coins, all with the heads facing down onto the table and the tails upward.
For exactly m times they select any k of the coins and toss them into the air, replacing each of them either heads-up or heads-down with the same possibility. Their purpose is to gain as many coins heads-up as they can.

输入

The input has several test cases and the ﬁrst line contains the integer t (1 ≤ t ≤ 1000) which is the total number of cases.
For each case, a line contains three space-separated integers n, m (1 ≤ n, m ≤ 100) and k (1 ≤ k ≤ n).

输出

For each test case, output the expected number of coins heads-up which you could have at the end under the optimal strategy, as a real number with the precision of 3 digits.

样例输入

样例输出

来源/分类

ICPC2017 Urumqi

题意：

给你n枚硬币（朝下）扔m次每次扔t枚问：最后向上的枚数的数学期望

分析：用dp求数学期望

dp[i][j]表示的是第i次扔完后 j枚硬币朝上的概率

有两种状态转移方程：

还有n-j枚为向下的优先扔它们

注：p[t] 为扔t次所有情况数分之一，c[][]算组合数

(1)n-j >= t

dp[i+1][j+k] += dp[i][j]*c[t][k]*p[t]

(2)n-j <k

dp[i+1][j-(t-(n-j))+k] += dp[i][j]*c[t][k]*p[t];

#include <bits/stdc++.h>
 
using namespace std;
 
double c[105][105];
double p[105];
double dp[105][105];
void init()
{
    c[0][0] = 1;
    for(int i=1;i<=100;i++)
    {
        c[i][0] = 1;
        for(int j=1;j<=i;j++)
        {
            c[i][j] = c[i-1][j-1]+c[i-1][j];
        }
    }
    p[0] = 1;
    for(int i=1;i<=100;i++)
    {
        p[i] = p[i-1]/2.0;
    }
}
int main()
{
    init();
    int T;
    cin>>T;
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        int n,m,t;
        cin>>n>>m>>t;
        dp[0][0] = 1;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<=n;j++)
            {
                if(dp[i][j]==0)
                    continue;
                for(int k=0;k<=t;k++)
                {
                    if(n-j>=t)
                        dp[i+1][j+k] += dp[i][j]*c[t][k]*p[t];
                    else
                        dp[i+1][j-(t-(n-j))+k] += dp[i][j]*c[t][k]*p[t];
                }
            }
        }
        double ans = 0;
        for(int i=1;i<=n;i++)
        {
            ans+=dp[m][i]*i;
        }
        printf("%.3f
",ans);
    }
}