本文主要是介绍zoj 4624，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目分析：有两排灯，每排n个，每个灯亮的概率为p，每个灯之间互不影响，亮了的灯不再灭，问两排中，每排有大于等于m个灯亮的概率。
设dp[ i ][ j ]为第一排亮了i个灯，第二排亮了j个灯，距离目标状态的期望天数。显然 i >= m ,j >= m时 ， dp[ i ][ j ] = 0 。
状态转移 :
第一排亮了a个灯，a 在[ 0 , n - i] 之间，第二排亮了b个灯 ， b 在[ 0 , n - j ] 之间。
则：
其中概率：
将dp[ i ][ j ]整理到等式的左边即可求出。
int n , m ;
double dp[58][58] ;
double c[58][58] ;
double go[58] ,notgo[58] ;int main(){int i , j , a , b ;c[0][0] = 1 ;for(i = 1 ; i <= 50 ; i++){c[i][0] = c[i][i] = 1 ;for(j = 1 ; j < i ; j++)c[i][j] = c[i-1][j] + c[i-1][j-1] ;}double p , sum ;while(cin>>n>>m>>p){if(n == 0 && m == 0 && p== 0) break ;memset(dp , 0 , sizeof(dp)) ;go[0] = 1.0 ;for(i = 1 ; i <= n ; i++) go[i] = go[i-1]*p ;notgo[0] = 1.0 ;for(i = 1 ; i <= n ; i++) notgo[i] = notgo[i-1]*(1.0 - p) ;for(i = n ; i >= 0 ; i--){for(j = n ; j >= 0 ; j--){if(i >= m && j >= m) continue ;sum = 1.0 ;for(a = 0 ; a <= n-i ; a++){for(b = 0 ; b <= n-j ; b++){if(a==0 && b==0) continue ;sum += dp[i+a][j+b]* c[n-i][a]*go[a]*notgo[n-i-a]*c[n-j][b]*go[b]*notgo[n-j-b] ;}}dp[i][j] = sum / (1.0 - notgo[n-i]*notgo[n-j]) ;}}printf("%.6lf\n" , dp[0][0]) ;}return 0 ;
}这篇关于zoj 4624的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
