UVa 542 - France '98

传送门

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;
}

Powered by Jekyll and Theme by solid