HDU 4870 Rating：高斯消元求期望比賽場次

問題描述

玩家有兩個賬號，初始 rating 均為 0。每次用分較低的賬號參賽：勝率 p，贏加 50 分，輸扣 100 分。直到某賬號達到 1000 分停止。求期望比賽場次。

建模與狀態壓縮

以 50 分為單位，目標為 20。狀態 (i, j) 表示兩賬號分數為 i, j（單位 50 分），且 i ≥ j。共 20*21/2 = 210 個狀態。設 f(i,j) 為從該狀態達到目標的期望場次。

狀態轉移方程

f(i,j) = 1 + p * f(i', j') + (1-p) * f(i'', j'')

其中：

• 贏：低分賬號加 1 單位 → 新狀態 (i, j+1) 若 j+1 ≤ i，否則 (j+1, i)（保持有序）。
• 輸：低分賬號減 2 單位 → (i, max(0, j-2))（不讓分數為負）。

邊界：i == 20 時 f=0。

線性方程組求解

210 個方程，210 個未知數，構造增廣矩陣 A[210][211]，高斯消元求解，答案為 f(0,0)。

代碼核心

const double EPS = 1e-9;
double a[215][215];
int id[21][21]; // 狀態到方程編號映射

void build(double p) {
    memset(a, 0, sizeof(a));
    int cnt = 0;
    for (int i=0; i<20; ++i)
        for (int j=0; j<=i; ++j)
            id[i][j] = cnt++;
    for (int i=0; i<20; ++i) {
        for (int j=0; j EPS) { pivot = k; break; }
        for (int j=i; j<=cnt; ++j) swap(a[i][j], a[pivot][j]);
        for (int j=0; jEPS) {
            double factor = a[j][i] / a[i][i];
            for (int k=i; k<=cnt; ++k) a[j][k] -= a[i][k] * factor;
        }
    }
    return a[0][cnt] / a[0][0];
}