2261:France '98

PKU

keyword

2進数　動的計画法　C++

概要

16チーム参加のトーナメントで、各チーム間の期待勝率が与えられる。各チームが優勝する確率を求める問題。
dp[チーム番号][n回戦を突破する確率]としてDP。n回戦で戦う可能性のあるチームはビットを使えば綺麗に求めることができる。

int main(){
    char names[16][40];
    int i, j, k, tar, base;
    int prob[16][16];
    double p[16][5];

    REP(i,16)REP(j,5) p[i][j] = 0.0;
    REP(i,16) p[i][0] = 1.0;
    REP(i,16)scanf("%s\n", names[i]);
    REP(i,16)REP(j,16) scanf("%d", prob[i]+j);

    REP(j,4){
        REP(i,16){
            base = (i^(1<<j)) & ~((1<<j)-1);
            REP(k,1<<j){
                tar = base | k;
                p[i][j+1] += p[i][j]*p[tar][j]*prob[i][tar]/100;
            }
        }
    }

    REP(i,16){
        printf("%s",names[i]);
        REP(j,11-strlen(names[i])) printf(" ");
        printf("p=%.2f\%\n",p[i][4]*100);
    }

    return  0;
}