poj3071–Football（概率计算）
分类：———-数学———-概率
题目链接：点击打开链接
题目大意：给出2^n个队伍，采用淘汰制比赛，第1和第2比赛，第2和第三比赛，淘汰之后，仍然按顺序比赛，p[i][j]：第i支队伍赢第j支队伍的概率，问最终哪个队伍赢的概率最大。
一共会比n场比赛，计算出每一个队伍赢得概率，找出最大值。
第一场 1对2，3对4，，，，
第二场1、2对3、4，5、6对7、8，，，，
第三场1、2、3、4对5、6、7、8，，
这样对于第i个队如果想要在第k场赢，，那么他需要在第k-1场赢的概率乘以∑（j在k-1场赢的概率*i对上j赢概率）
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std ;#define eqs 1e-8double p[200][200] ;double ans[200][200] ;int main() {int n , m ;int i , j , len , k , l , r , mid ;double temp ;while( scanf("%d", &n) && n != -1 ) {m = 1<<n ;for(i = 1 ; i <= m ; i++) ans[n][i] = 1.0 ;for(i = 1 ; i <= m ; i++)for(j = 1 ; j <= m ; j++)scanf("%lf", &p[i][j]) ;len = 2 ;while( n– ) {k = 1 ;while( k*len <= m ) {l = 1+(k-1)*len ;r = k*len ;mid = (l+r) / 2 ;for(i = l ; i <= r ; i++) {temp = 0.0 ;if( i <= mid ) {for(j = mid+1 ; j <= r ; j++)temp += ans[n+1][j]*p[i][j] ;ans[n][i] = ans[n+1][i]*temp ;}else {for(j = l ; j <= mid ; j++)temp += ans[n+1][j]*p[i][j] ;ans[n][i] = ans[n+1][i]*temp ;}}k++ ;}len *= 2 ;}temp = ans[0][1] ;k = 1 ;for(i = 2 ; i <= m ; i++) {if( ans[0][i]-temp >= eqs ) {temp = ans[0][i] ;k = i ;}}printf("%d\n", k) ;}return 0 ;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇poj1222–EXTENDED LIGHTS OUT(高斯消元)
顶0踩0
只有流过血的手指才能弹出世间的绝唱。
