2017 ICPC乌鲁木齐 A Coins 概率dp

题意：一开始所有n个硬币都是反面朝上的，每次必须拿k个来抛，抛的人足够聪明，问m次之后向上的硬币的期望。

首先说了这个足够聪明的意思，就是只要向反面的有k个就不会sb地去拿向正面的来抛，想了一会之后就觉得是个概率dp的转移，

然而一开始想漏了个组合数的加权，但在+1的提醒下搞通了，但是分析了下，这是nmk的时间复杂度，

1e6还有个1e3的大T,emmm理论上会TLE的，但结果看网上题解，都是跟自己思路差不多，所以也是很迷。

嗯，转移过程其实很简单，dp[i][j]就是第i次抛了之后j个硬币向上的概率，所以如果n-j>=k很明显，这是全部拿向反面的来抛就行，那么dp[i+1][j+kk]=dp[i][j]*0.5的k次方*k个里面有kk个向正面的组合数

而n-j<的话，那么就得那一些向正面的来抛了，剩下的正面的就j-(k-(n-j))也就是n-k个，那么dp[i+1][n-k+kk]=dp[i][j]*0.5的k次方*k个里面有kk个向正面的组合数

 #include<cstdio>

 const int N=;

 double cf05[N],c[N][N],dp[N][N];

 void init(){

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

         c[i][]=1.0;

         for(int j=;j<=i;j++){

             if(j<=i/) c[i][j]=c[i-][j-]+c[i-][j];

             else c[i][j]=c[i][i-j];

         }

     }

     cf05[]=1.0;

     for(int i=;i<=;i++) cf05[i]=cf05[i-]*0.5;

 }

 int main(){

     init();

     int t,n,m,k;

     scanf("%d",&t);

     while(t--){

         scanf("%d%d%d",&n,&m,&k);

         for(int i=;i<=m;i++)

             for(int j=;j<=n;j++) dp[i][j]=0.0;

         dp[][]=1.0;

         for(int i=;i<m;i++){

             for(int j=;j<=n;j++){

                 if(dp[i][j]==0.0) continue;

                 for(int kk=;kk<=k;kk++){

                     if(n-j>=k) dp[i+][j+kk]+=dp[i][j]*cf05[k]*c[k][kk];

                     else dp[i+][n-k+kk]+=dp[i][j]*cf05[k]*c[k][kk];

                 }

             }

         }

         double ans=0.0;

         for(int i=;i<=n;i++) ans+=dp[m][i]*i;

         printf("%.3f\n",ans);

     }

     return ;

 }

怪怪的哦

巴特西

2017 ICPC乌鲁木齐 A Coins 概率dp

最新文章

热门文章