UVa 542 - France '98
传送门
题意
16个队比赛,给出每个队碰面时候的胜率,求每个队获得冠军的概率。
思路
不知道怎么处理队和队的关系。参考了林燕同学 的题解才知道可以用队伍号 / 轮数来判断可不可以打,而且以前已经打过的队伍不能再打。
代码
#include <bits/stdc++.h>
using namespace std;
double dp[20][10]; //the probablity of ith team advanced to the jth round
int prob[20][20], rec[5];
char name[20][100];
double DFS(int n, int r)
{
double &cur = dp[n][r];
if (cur != -1)
return cur;
cur = 0;
for (int i = 0; i < 16; i++)
if (i / rec[r] == n / rec[r] && i / rec[r - 1] != n / rec[r - 1])
cur += DFS(n, r - 1) * DFS(i, r - 1) * prob[n][i] * 1.0 / 1e4;
return cur;
}
int main()
{
//freopen("input.txt", "r", stdin);
int i, j, k, n;
for (i = 0; i < 16; i++)
for(j = 1; j <= 4; j++)
dp[i][j] = -1;
rec[0] = 1;
for (i = 1; i <= 4; i++)
rec[i] = rec[i - 1] * 2;
for (i = 0; i < 16; i++)
{
dp[i][0] = 100;
scanf("%s", name[i]);
}
for (i = 0; i < 16; i++)
for (j = 0; j < 16; j++)
scanf("%d", &prob[i][j]);
for (i = 0; i < 16; i++)
DFS(i, 4);
for (i = 0; i < 16; i++)
printf("%-10s p=%.2f%%\n", name[i], dp[i][4]);
return 0;
}