Codeforces 167B：巫師與巨大獎品 - 概率動態規劃詳解

題目大意

有 n 個對手，至少需擊敗 l 個。初始背包容量為 k。每個對手有獲勝機率 p[i]，擊敗後：若 a[i] = -1 獲得一枚金幣（佔用 1 容量）；若 a[i] > 0 則背包容量永久增加 a[i]。求最終「擊敗數 ≥ l」且「背包剩餘容量 ≥ 0」的總概率。

狀態定義與轉移

定義 dp[i][j][c]：考慮前 i 個對手，已擊敗 j 個，當前剩餘容量為 c 的概率。容量可能為負，故引入偏移量 OFFSET = 200（因 n ≤ 200，容量變化範圍在 [-200, 200]）。

轉移方程：

• 擊敗第 i 個對手：dp[i][j+1][c + delta] += dp[i-1][j][c] * p[i]，其中 delta = (a[i]==-1 ? -1 : a[i])。
• 未擊敗：dp[i][j][c] += dp[i-1][j][c] * (1 - p[i])。

代碼實現

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

const int MAXN = 205;
const int OFFSET = 200; // 偏移量，使容量索引非負

int n, l, k;
double p[MAXN];
int a[MAXN];
double dp[MAXN][MAXN][2*MAXN]; // dp[i][j][c+OFFSET]

int main() {
    while (scanf("%d%d%d", &n, &l, &k) == 3) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lf", &p[i]);
            p[i] /= 100.0;
        }
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

        memset(dp, 0, sizeof(dp));
        dp[0][0][k + OFFSET] = 1.0; // 初始容量 k

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                for (int c = 0; c <= 2*OFFSET; ++c) {
                    double cur = dp[i-1][j][c];
                    if (cur == 0) continue;
                    // 不擊敗
                    dp[i][j][c] += cur * (1 - p[i]);
                    // 擊敗
                    int nc = c;
                    if (a[i] == -1) nc--;
                    else nc += a[i];
                    if (nc > 2*OFFSET) nc = 2*OFFSET; // 容量上限截斷
                    if (nc >= 0)
                        dp[i][j+1][nc] += cur * p[i];
                }
            }
        }

        double ans = 0;
        for (int j = l; j <= n; ++j)
            for (int c = OFFSET; c <= 2*OFFSET; ++c)
                ans += dp[n][j][c];

        printf("%.6f\n", ans);
    }
    return 0;
}

關鍵優化點

• 偏移量技巧處理負數容量索引。
• 容量上限截斷避免數組越界（實際容量超過 2*OFFSET 視同無上限）。
• 滾動數組可優化空間至 O(n * C)，但 n=200 時三維數組仍可接受。

總結

本題是典型的「背包容量動態變化」概率 DP，核心在於狀態設計與偏移量處理負數索引。同類問題常見於 Codeforces、AtCoder 等比賽。