UVA542 - France '98(dp)

UVA542 - France '98(dp)
제목 링크
제목 대의: 이전에 제목의 뜻을 이해한 줄 알았는데 사실 이해하지 못했다. 각 선수를 각자 있는 구역에 나누었다. 이것은 첫 번째 PK의 조별이 확정되었음을 의미한다. 그리고 우승자는 반드시 두 개의 좌우 구역에서 나온 승리자만이 Pk우승을 할 기회가 있다는 것을 의미한다.문제풀이 사고방식: 그러면 1-16이라는 큰 구간에서 탄생한 우승자는 왼쪽에서 왔을 수도 있고 오른쪽에서 왔을 수도 있다. 그리고 왼쪽 오른쪽의 자구간에서 우승자를 찾아낸다.f[i][l][r]는 l-r 이 구간의 승리자가 i의 확률을 나타낸다. 그러면 i가 구간의 가장 왼쪽에 있다고 가정하고 f[i][l]=Sum(f[i][l][m][m][m][m+1][r][r][i][k](k는 [m+1,r])에 속한다.i 우승을 요구하면 왼쪽 우승은 확정되지만 오른쪽 우승은 미정이다.그리고 i를 타고 k를 물리칠 확률p.상황은 오른쪽에서 유사하다.
코드:

#include <cstdio>
#include <cstring>
#include <cmath>

const int maxn = 16;
char name[maxn][maxn];
double p[maxn][maxn];
double f[maxn][maxn][maxn];
double esp = 1e-9;

void init () {

    for (int i = 0; i < maxn; i++)
        for (int j = 0; j < maxn; j++)
            for (int k = 0; k < maxn; k++)
                f[i][j][k] = -1.0;
}

double dp (int k, int l, int r) {

    double& ans = f[k][l][r];

    if (ans > 0)
        return ans; 
    if (r - l == 1)
        return ans = p[k][k == l?r:l];

    int m = (l + r)>>1;
    double tmp;
    ans = 0;

    if (k <= m) { 
        tmp = dp(k, l, m);    
        for (int i = m + 1; i <= r; i++)
            ans += p[k][i] *  tmp * dp(i, m + 1, r);
    } else {

        tmp = dp(k, m + 1, r);
        for (int i = l; i <= m; i++)
            ans += p[k][i] * tmp * dp(i, l, m);
    }
    return ans;
}

int main () {

    while (scanf ("%s", name[0]) != EOF) {

        for (int i = 1; i < maxn; i++)
            scanf ("%s", name[i]);

        int P;
        for (int i = 0; i < maxn; i++)
            for (int j = 0; j < maxn; j++) {
                scanf ("%d", &P);
                p[i][j] = P/100.0;
            }

        init();
        for (int i = 0; i < maxn; i++)
            printf ("%-10s p=%.2lf%
", name[i], dp(i, 0, maxn - 1) * 100.0);

    }
    return 0;
}