挺不错的概率DP，看似基础，实则很考验扎实的功底
这题很明显是个DP，为什么？？？找规律或者算组合数这种概率，N不可能给的这么友善。。。
因为DP一般都要在支持N^2操作嘛。
稍微理解一下，这DP[i][j]还是不好想啊，首先是写DP[I][j]的含义
首先我们想这道题是要求一个最优决策下的期望，那么这个我们的最优决策是什么？？？
决策就是：我们假设我这一次需要翻转K个硬币，我们不愿翻那些已经在正面的，而去翻那些没有在正面的
而如果剩余的反面的不足，我再去翻转正面的
那么给dp[i][j]一个含义，代表我现在进行第i轮，已经翻转了j个正面了，并用一个K表示我当前这一轮有K个正面朝上，再写出转移方程
dp[i+1][j+k]=dp[i][j]*C(z,i)*pow(0.5,z);
C(z,k)*pow(0.5,z);就代表，这一次需要在Z个硬币中，翻转上来K个的概率
而如果出现剩余面不足，我翻转反面，相减就可以
注意POW会超时，写一个p[i]的数组，表示（1/2）^i就可以了
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
double c[][];
double dp[][];
double p[];
int main()
{
int n,m,k;
int t,z;
scanf("%d",&t);
int tmp1,tmp2,tmp3;
c[][]=;
for (int i=;i<=; i++)
{
c[i][]=;
for (int j=;j<=i;j++)
{
c[i][j]=c[i-][j-]+c[i-][j];
}
}
p[]=;
for (int i=;i<=;i++){
p[i]=p[i-]*0.5;
}
while(t--)
{
scanf("%d%d%d",&n,&m,&z);
memset(dp,,sizeof(dp));
dp[][]=;
for (int i=; i<m; i++)//本轮
{
for (int j=; j<=n; j++)//已经有j面向下了
{
if(dp[i][j]==)continue;
for (int k=; k<=z; k++)//如果在这t枚中得到了k个向下的
{
if (j+z<=n)//全选面向下的
dp[i+][j+k]+=dp[i][j]*p[z]*c[z][k];
else //选完剩余的还要选已经向上的
dp[i+][k+n-z]+=dp[i][j]*p[z]*c[z][k];
}
}
}
double ans=;
for (int i=;i<=n;i++){
ans+=dp[m][i]*i;
}
printf("%.3lf\n",ans);
}
return ;
}