LightOJ 1027 A Dangerous Maze：期望 DP 迷宮逃脫

題目描述

n 扇門，等概率選擇。第 i 扇門：x_i > 0 表示 x_i 分鐘出去；x_i < 0 表示 |x_i| 分鐘回到起點（失去記憶）。求期望逃脫時間，分數形式 p/q（最簡），不可能輸出 inf。

數學推導

設期望為 E。
出門機率 p_pos = k/n（k 為正數個數），平均出門時間 avg_pos = sum_pos/k。
回門機率 p_neg = (n-k)/n，平均回門時間 avg_neg = sum_neg/(n-k)。
方程：E = p_pos * avg_pos + p_neg * (avg_neg + E)。
解得：E = (sum_pos + sum_neg) / k = total_time / k。
若 k=0（全負），輸出 inf。

C++ 代碼實現

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T; scanf("%d", &T);
    for (int cs=1; cs<=T; ++cs) {
        int n; scanf("%d", &n);
        long long sum = 0, posCnt = 0;
        for (int i=0; i 0) ++posCnt;
        }
        if (posCnt == 0) {
            printf("Case %d: inf\n", cs);
        } else {
            long long g = __gcd(sum, posCnt);
            printf("Case %d: %lld/%lld\n", cs, sum/g, posCnt/g);
        }
    }
    return 0;
}

關鍵點

• 期望公式推導簡潔，最終只需總絕對時間除以正門數。
• 分數化簡用 gcd。
• 輸入有空行，scanf 自動跳過。