POJ 3071 Football（簡單 概率DP）

POJ 3071 Football（簡單 概率DP）

大意：2^n 個球隊進行單場淘汰賽，每兩只球隊之間比賽會有勝負的概率，問最後誰奪冠的概率最大。

思路：簡單的概率DP問題，主要是怎麼處理哪兩個球隊比賽的問題。

DP方程為 dp[i][j] = ∑(dp[i-1][j]*dp[i-1][k]*p[j][k]); //dp[i][j]表示第 i 輪的時候，第 j 支隊伍贏的概率。、

對於其中位運算，可以用一個二叉樹來更直觀的理解 (j>>(i-1))^1) 跟 (k>>(i-1)分別表示一個父節點的兩個子節點， 當(j>>(i-1))^1) == (k>>(i-1)時，表明兩個子節點是競爭關系，勝利者將更新到復接點。

#include 
#include 

int n;
double p[1000][1000];
double dp[10][1000];

int main()
{
    while(~scanf(%d, &n) && n != -1){
        for(int i = 0; i < (1<>(i-1))^1) == (k>>(i-1)))
                        dp[i][j] += dp[i-1][k]*dp[i-1][j]*p[j][k];
                }
            }
        }

        double ans = -1;
        int Ans = -1;
        for(int i = 0; i < (1< ans){
                ans = dp[n][i];
                Ans = i;
            }
        }
        printf(%d
, Ans+1);
    }

    return 0;
}