[动态规划][概率dp]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 first 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.

 

样例输入

6
2 1 1
2 3 1
5 4 3
6 2 3
6 100 1
6 100 2

 

样例输出

0.500
1.250
3.479
3.000
5.500
5.000
思路：概率dp;状态dp[i][j]表示i次操作后，有j枚硬币正面朝上的概率；初步考虑状态转移方程为：dp[i][j]=sum{r=1~n  dp[i-1][r] * [C(k,j-r)/(2^k)]}
但其实不对，首先要分类j>=r和j<r两种情况；
j>=r的时候很好想，根据最优策略(优先选择正面朝下的硬币翻转):
当n-r>=k时，从n-r中任选k个硬币翻转，k个硬币中有(j-r)个硬币正面朝上的概率为C(k,j-r)/2^k，所以此时dp[i][j]+=dp[i-1][r] * [C(k,j-r)/2^k];
当n-r<k时，从n-r中选n-r个，从r中选k-(n-r)个硬币翻转，k个硬币中j-r+k-(n-r)正面朝上的概率为P(计算同上),此时dp[i][j]+=dp[i][r]*P;
j<r时，根据最优策略：
当n-r>=k时，continue；
当n-r<k时，从n-r中选n-r个，从r中选k-(n-r)个硬币翻转，当r-[k-(n-r)]>j时，continue；否则，k个硬币中要有j-{r-[k-(n-r)]}个硬币正面朝上，
AC代码：

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;

double f[110];
double dp[110][110];
double pow[110];
double c[110][110];

void init(){
  pow[0]=1;c[0][0]=1;
  for(int i=1;i<=100;i++) {
        pow[i]=pow[i-1]*1.0/2.0;
        c[i][0]=1;for(int j=1;j<=i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j];
  }
}

int main()
{
    init();
    int t;scanf("%d",&t);
    while(t--){
        int n,m,k;scanf("%d%d%d",&n,&m,&k);
        memset(dp,0,sizeof(dp)); dp[0][0]=1;
        for(int i=1;i<=m;i++){
            for(int j=0;j<=n;j++){
                for(int r=0;r<=n;r++){
                    if(j>=r){
                        if(n-r>=k) {
                                dp[i][j]+=(dp[i-1][r]*c[k][j-r]*1.0*(pow[k]*1.0));
                        }
                        else dp[i][j]+=(dp[i-1][r]*c[k][j-r+(k-(n-r))]*1.0*(pow[k]*1.0));
                    }
                    else{
                        if(n-r>=k) continue;
                        else{
                            if(r-(k-(n-r))>j) continue;
                            else dp[i][j]+=(dp[i-1][r]*c[k][j-(r-(k-(n-r)))]*1.0*(pow[k]*1.0));
                        }
                    }
                }
            }
        }
        double ans=0;
        for(int i=0;i<=n;i++) ans+=i*dp[m][i];
        printf("%.3fn",ans);
    }
    return 0;
}

 

（图片参考：https://www.cnblogs.com/hrhguanli/p/3960520.html）