【POJ 3071】 Football

【题目链接】
【算法】
概率DP
f[i][j]表示第j支队伍进入第i轮的概率,转移比较显然
【代码】
#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

int i,j,k,n,pos;

double a[][],f[][];

int main()

{

        while (scanf("%d",&n) != EOF && n != -)

        {

                memset(f,,sizeof(f));

                for (i = ; i <= ( << n); i++)

                {

                        for (j = ; j <= ( << n); j++)

                        {

                                scanf("%lf",&a[i][j]);

                        }

                }

                for (i = ; i <= ( << n); i++) f[][i] = 1.0;

                for (i = ; i <= n + ; i++)

                {

                        for (j = ; j <= ( << n); j++)

                        {

                                for (k = ; k <= ( << n); k++)

                                {

                                        if ((((j - ) >> (i - )) ^ ) == ((k - ) >> (i - )))

                                                f[i][j] += f[i-][k] * f[i-][j] * a[j][k];

                                }

                        }

                }

                pos = ;

                for (i = ; i <= ( << n); i++)

                {

                        if (f[n+][i] > f[n+][pos])

                                pos = i;

                }

                printf("%d\n",pos);

        }

        return ;

}