您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 4418 Time Travel：高斯消元 + 概率 DP 期望求解

編輯：C++ 入門

題目大意

N 個點環狀排列 (0~N-1)。從起點 st 出發，每步按概率 p[i] 選擇步長 i (1≤i≤m)。到達終點 ed 或其對稱點 n-ed 即結束。求期望步數。不可達輸出 "Impossible !"。

關鍵建模：狀態空間展開

環上隨機游走有周期性。將 0~N-1 展開為 0~2N-3 的線段：

原環: 0 - 1 - 2 - ... - (N-1) - 0
展開: 0 - 1 - 2 - ... - (N-1) - N - (N+1) - ... - (2N-3)
           ↑                                    ↑
          st                                   對稱點

其中節點 i 和 2N-2-i 為對稱點 (對應環上同一物理位置)。終止狀態：ed 和 2N-2-ed。

狀態方程：期望線性方程組

設 E[x] 為從狀態 x 到達終止狀態的期望步數。

對於非終止狀態 x：

E[x] = 1 + Σ p[i] × E[(x+i) mod (2N-2)]

整理為標準線性方程組：

(1 - p[0])E[x] - Σ p[i]E[next] = 1 (p[0] 通常為 0)

終止狀態：E[ed] = 0, E[2N-2-ed] = 0

高斯消元求解

方程組大小 ≤ 2N-2 ≤ 200 (N≤100)。高斯消元 O(n³) 完全足夠。

完整代碼實現

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

const double EPS = 1e-9;
const int MAXN = 220;

double a[MAXN][MAXN]; // 增廣矩陣 [n][n+1]
int n, m, st, ed, d;
double p[105];
int id[MAXN], cnt;    // 狀態映射：物理節點 -> 方程變量索引

// 高斯消元：返回 0 無解/無限解，1 唯一解
int gauss(int n) {
    for (int col = 0, row = 0; col < n && row < n; ++col, ++row) {
        // 選主元：絕對值最大行
        int sel = row;
        for (int i = row; i < n; ++i)
            if (fabs(a[i][col]) > fabs(a[sel][col])) sel = i;
        if (fabs(a[sel][col]) < EPS) { --row; continue; } // 自由變量
        
        if (sel != row) swap(a[sel], a[row]); // 換行
        
        // 歸一化當前行
        double div = a[row][col];
        for (int j = col; j <= n; ++j) a[row][j] /= div;
        
        // 消去其他行
        for (int i = 0; i < n; ++i) if (i != row) {
            double factor = a[i][col];
            if (fabs(factor) < EPS) continue;
            for (int j = col; j <= n; ++j)
                a[i][j] -= factor * a[row][j];
        }
    }
    
    // 檢查無解：0 = 非0
    for (int i = 0; i < n; ++i) {
        bool allZero = true;
        for (int j = 0; j < n; ++j)
            if (fabs(a[i][j]) > EPS) { allZero = false; break; }
        if (allZero && fabs(a[i][n]) > EPS) return 0; // 0 = c (c≠0)
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        cin >> n >> m >> ed >> st >> d;
        for (int i = 1; i <= m; ++i) {
            cin >> p[i]; p[i] /= 100.0;
        }
        
        if (ed == st) { cout << "0.00\n"; continue; }
        
        int N = 2 * n - 2; // 展開後總節點數
        if (d == 1) st = N - st; // 方向調整
        
        // BFS 確定可達狀態
        memset(id, -1, sizeof(id));
        queue<int> q;
        q.push(st); id[st] = cnt++;
        if (id[N-ed] == -1) { q.push(N-ed); id[N-ed] = cnt++; } // 對稱終點
        if (id[ed] == -1) { q.push(ed); id[ed] = cnt++; }
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 1; i <= m; ++i) if (p[i] > EPS) {
                int v = (u + i) % N;
                if (id[v] == -1) { id[v] = cnt++; q.push(v); }
            }
        }
        
        // 檢查終點可達
        if (id[ed] == -1 && id[N-ed] == -1) {
            cout << "Impossible !\n"; continue;
        }
        
        // 建立方程組
        memset(a, 0, sizeof(a));
        for (int u = 0; u < N; ++u) if (id[u] != -1) {
            int row = id[u];
            if (u == ed || u == N-ed) { // 終止狀態
                a[row][row] = 1;
                a[row][cnt] = 0;
                continue;
            }
            a[row][row] = 1.0;
            for (int i = 1; i <= m; ++i) if (p[i] > EPS) {
                int v = (u + i) % N;
                if (id[v] == -1) continue; // 不可達狀態不建立方程
                a[row][id[v]] -= p[i];
                a[row][cnt] += i * p[i]; // 期望步長加權
            }
        }
        
        if (!gauss(cnt)) { cout << "Impossible !\n"; continue; }
        
        double ans = a[id[st]][cnt];
        cout << fixed << setprecision(2) << ans << "\n";
    }
    return 0;
}