中石油多校联赛（最后一水）Pong’s Birds（dp）

题目描述

In order to train his birds, Pong is holding a competition for them. (He have birds, does he?) He have 2n  birds, so he want to hold elimination series. Literally, if n = 2 and he has 4 birds identified as 1,2,3,4, he would first hold  competition for 1 and 2, 3 and 4, the one fails would be eliminated and then he holds competition for the winners.  According to his long observation, for each pair of birds he knows the probability to win for each bird, and he  want to know the probability of each bird to be the final winner.

输入

For the first row there is an integer T(T ≤ 100), which is the number of test cases. For each case , first row is an integer n(1 ≤ n ≤ 7), for the next 2n  rows , each row has 2n  real numbers as the  probability to win for the i-th when competed to j-th bird. It is promised that for each i, j p[i][j] + p[j][i] = 1 and  p[i][i] = 0;

输出

For each case you should output a line with 2n  real numbers, which is the probability of i-th bird be the final  winner. Rounded to 3 decimal places. Make sure to output a space character after each number, to prevent the Presentation Error.

样例输入

1 1 0 0.5 0.5 0

样例输出

0.500 0.500

状态转移方程：

dp[i][j] += dp[i-1][j]*map[j][k]*dp[i-1][k];

其中dp]i][j]表示第i场比赛第j个bird胜利的概率，如果要求dp[i][j]，则要求出dp[i-1][j]的概率，假设和第i次和第k个bird比较，则要计算出map[j][k]和dp[i-1][k]，结果相乘即可，

#include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; double dp[150][150],map[150][150];//dp[i][j]表示第i场比赛第j个bird胜利的概率 int t,n; int main(){ scanf("%d",&t); while(t --){ scanf("%d",&n); memset(dp,0,sizeof(dp)); int maxn = pow(2,n); for(int i = 1; i <= maxn; i ++) dp[0][i] = 1; for(int i = 1; i <= maxn; i ++){ for(int j = 1; j <= maxn; j ++) scanf("%lf",&map[i][j]); } for(int i = 1; i <= n; i ++){ //比赛的场数，即表示第i场比赛 for(int j = 1; j <= maxn; j ++){//第j个bird胜利 int l = pow(2,i-1); //maxn/l表示剩下的个数，所以1/l表示为maxn的多少倍 int r = l * 2; int temp = ceil(j*1.0/l);//表示第j个bird在经过i场比赛后的位置 if(temp%2){//当前位为奇数位，则一定要和后面偶数位的比较 for(int k = temp*l+1; k <= temp*l+r-l; k ++){//确定k的取值范围。 dp[i][j] += dp[i-1][j]*map[j][k]*dp[i-1][k]; } } else{//当前位为偶数位，则要和前面的奇数位比较 for(int k = (temp-1)*l; k > (temp-1)*l - (r-l); k --){ dp[i][j] += dp[i-1][j]*map[j][k]*dp[i-1][k]; } } } } printf("%.3f",dp[n][1]); for(int i=2;i<=maxn;i++) printf(" %.3f",dp[n][i]); putchar('\n'); } return 0; }