首页 > 代码库 > zoj 2949 - Coins of Luck
zoj 2949 - Coins of Luck
题目:有2中面条各n碗。每次抛硬币推断吃哪一种(到一种吃完为止)。问抛硬币的数学期望。
分析:动态规划。概率dp。求出每种结束状态(即,有一种吃完)的概率,分别乘以步长即为期望。
大黄解法:状态位剩余的碗数,逆向求解,状态方程:
DP[ i ][ j ] = (DP[ i-1 ][ j ]+DP[ i ][ j-1 ])/2 + 1 { orz~~ (所有20行代码就能搞定) }。
说明:(2011-09-27 03:22)。
#include <stdio.h> #include <stdlib.h> double p[ 1002 ][ 1002 ]; double q[ 1002 ]; int main() { for ( int i = 0 ; i <= 1000 ; ++ i ) for ( int j = 0 ; j <= 1000 ; ++ j ) p[ i ][ j ] = 0.0; p[ 0 ][ 0 ] = 1.0; for ( int i = 0 ; i <= 1000 ; ++ i ) for ( int j = 0 ; j <= 1000 ; ++ j ) { p[ i+1 ][ j ] += p[ i ][ j ]*0.5; p[ i ][ j+1 ] += p[ i ][ j ]*0.5; } for ( int i = 1 ; i <= 1000 ; ++ i ) { double sum = p[ i ][ 0 ]*i; for ( int j = i-1 ; j >= 1 ; -- j ) sum += (i+j)*(p[ i ][ j ]-p[ i ][ j-1 ]*0.5); q[ i ] = sum*2.0; } int t,n; while ( scanf("%d",&t) != EOF ) while ( t -- ) { scanf("%d",&n); printf("%.2lf\n",q[ n ]); } return 0; }
zoj 2949 - Coins of Luck
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。