poj 3071 Football（概率dp）

id=3071">http://poj.org/problem?

id=3071

大致题意：有2^n个足球队分成n组打比赛。给出一个矩阵a[][],a[i][j]表示i队赢得j队的概率。n次比赛的流程像这样

action=showproblem&problemid=2304">France \'98

。

问最后哪个队最可能得冠军。

思路：概率dp问题。ans[i][j]表示第i轮中j队获胜的概率。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#define LL long long
#define _LL __int64
#define eps 1e-8

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 10;

int n;
int m;
double a[130][130];
double ans[maxn][130];
int pow2[8] = {1,2,4,8,16,32,64,128};

void solve()
{
	memset(ans,0,sizeof(ans));
	int t,r;

	for(int i = 1; i <= m; i++)
	{
		if(i&1)
			ans[1][i] = a[i][i+1];
		else
			ans[1][i] = a[i][i-1];
	}

	for(int i = 2; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			r = pow2[i]; //周期
			if(j % r == 0) t = j/r;
			else t = j/r+1;

			if(j%r >= 1 && j%r <= r/2)
			{
				for(int k = t*r; ; k--)
				{
					if(k%r != 0 && k%r <= r/2)
						break;
					ans[i][j] += ans[i-1][j]*a[j][k]*ans[i-1][k];
				}
			}

			else
			{
				for(int k = (t-1)*r+1; ; k++)
				{
					if(k%r >= r/2+1)
						break;

					ans[i][j] += ans[i-1][j]*a[j][k]*ans[i-1][k];
				}
			}
		}
	}

}

int main()
{
	while(~scanf("%d",&n))
	{
		if(n == -1) break;
		m = pow2[n];

		for(int i = 1; i <= m; i++)
			for(int j = 1; j <= m; j++)
				scanf("%lf",&a[i][j]);

		solve();

		double res = ans[n][1];
		int pos = 1;

		for(int i = 2; i <= m; i++)
		{
			if(res < ans[n][i])
			{
				res = ans[n][i];
				pos = i;
			}
		}
		printf("%d\n",pos);
	}
	return 0;
}