POJ 2151 題目難度檢測：機率動態規劃完整解析

題目大意

ACM 比賽中有 T 隊伍、m 道題目。每隊解出每題的機率已知。求：每隊至少解出一題 且 冠軍隊（第 1 隊）至少解出 n 題 的總機率。

核心思路：兩層動態規劃

第一層 DP：單隊解題數機率分布

定義 x[i][j][k]：第 i 隊在前 j 道題中恰好解出 k 題的機率。轉移方程：

x[i][j][k] = x[i][j-1][k-1] * p[i][j] + x[i][j-1][k] * (1 - p[i][j])

邊界條件：

• x[i][0][0] = 1（0 題解出 0 題機率為 1）
• x[i][j][0] = ∏(1 - p[i][t])（前 j 題全不解）

計算完後，x[i][m][k] 即為第 i 隊恰好解出 k 題的機率。

第二層 DP：隊伍序列與冠軍解題數狀態

定義 d[i][j]：處理前 i 隊，冠軍隊目前解出題數為 j 的機率。遞歸轉移：

d[i][j] = Σ_{k=1..m} d[i+1][max(j, k)] * x[i][m][k]

意義：第 i 隊解出 k 題，更新冠軍隊最大解題數為 max(j, k)。注意題目要求「每隊至少解一題」，故 k 從 1 開始累加（k=0 不合法）。

邊界：i == T+1 時，若 j >= n 回傳 1，否則 0。最終答案為 d[1][0]。

程式碼實現要點

• 使用遞歸 + 記憶化（vis[][] 時間戳標記）實現第二層 DP，避免重複計算。
• 機率陣列 a[i][j] 1-based 索引對應題目輸入。
• 雙層 DP 時間複雜度：O(T * m^2 + T * m * n)，滿足資料範圍。
• 輸出格式：printf("%.3f\n", ans) 保留三位小數。

完整程式碼

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 1000 + 10;
int T, n, m, vis[maxn][33], kase = 0;
double a[maxn][33], x[maxn][33][33], d[maxn][33];

double dp(int i, int j) {
    double& ans = d[i][j];
    if (i == T + 1) return j >= n;
    if (vis[i][j] == kase) return ans;
    vis[i][j] = kase;
    ans = 0;
    for (int k = 1; k <= m; k++) {
        ans += dp(i + 1, max(j, k)) * x[i][m][k];
    }
    return ans;
}

int main() {
    while (~scanf("%d%d%d", &m, &T, &n) && (m || T || n)) {
        for (int i = 1; i <= T; i++)
            for (int j = 1; j <= m; j++)
                scanf("%lf", &a[i][j]);
        memset(x, 0, sizeof(x));
        ++kase;
        for (int i = 1; i <= T; i++) {
            x[i][0][0] = 1;
            for (int j = 1; j <= m; j++)
                x[i][j][0] = x[i][j-1][0] * (1 - a[i][j]);
            for (int j = 1; j <= m; j++)
                for (int k = 1; k <= j; k++) {
                    x[i][j][k] = x[i][j-1][k-1] * a[i][j];
                    if (j-1 >= k)
                        x[i][j][k] += x[i][j-1][k] * (1 - a[i][j]);
                }
        }
        double ans = dp(1, 0);
        printf("%.3f\n", ans);
    }
    return 0;
}