【Codeforces-167B】Wizards and Huge Prize • TonyYin's Blog

题目地址：CF167B - Wizards and Huge Prize - 洛谷 ↗

题意#

最开始，你有 $M$ 的容积。有 $n$ 轮比赛，对于第 $i$ 场比赛，你获胜的概率为 $p_i$ .

比赛的奖励分为两种：一种是增加 $a_i$ 的容积，一种是给你 $1$ 个奖品。

一种赢比赛的合法方案，需要满足： $n$ 轮比赛结束时，总容积 $\geq$ 获得的奖品数量。

求获胜场次 $\geq l$ ，且方案合法的概率。

$1\leq M, n, a_i\leq 200$ ， $0\leq p_i\leq 1$ .

题解#

概率 DP。

显然，获得一个奖品等价于容积 $-1$ ，方案合法 $\Leftrightarrow$ $n$ 轮结束后的容积非负。

设 $\operatorname{dp}_{i, j, k}$ 表示：前 $i$ 轮比赛后，在其中的 $j$ 场中获胜，当前可用容积为 $k$ 发生的概率。

为了方便表示，允许下标为负，则：

\operatorname{Ans} = \sum_{i=l}^{n}\sum_{j=0}^{+\infty}{\operatorname{dp}_{n,i,j}}

第三维数组的大小？

注意到，每次操作最多减 $1$ ，如果容积 $>=n$ ，就不可能不合法了，都和 $n$ 的状态等价。

所以有意义的可用容积在 $[-n, n]$ 范围内，空间开 $2\times n$ 即可，答案的表达式也可以改写为：

\operatorname{Ans} = \sum_{i=l}^{n}\sum_{j=0}^{n}{\operatorname{dp}_{n,i,j}}

考虑如何转移？

刷表，状态 $(i, j, k)$ 只会贡献到 $(i+1, j, k)$ 或 $(i+1, j+1, \min\{n, k+a_{i+1}\})$ .

两种转移分别对应 赢/不赢 第 $i+1$ 轮，具体地：

\begin{array}{rcl} (1-p_{i+1})\times \operatorname{dp}_{i,j,k}&\rightarrow &\operatorname{dp}_{i+1,j,k}\\ p_{i+1}\times \operatorname{dp}_{i,j,k}&\rightarrow &\operatorname{dp}_{i+1, j+1, \min\{n,k+a_{i+1}\}} \end{array}

时空复杂度均为 $\mathcal{O}(n^3)$ .

代码#

实现时，注意将第三维坐标整体 $+n$ .

const int N = 200;

dp[0][0][N + K] = 1.0;
for(int i = 0; i < n; i++) {
    for(int j = 0; j <= i; j++) {
        for(int k = 0; k <= (N << 1); k++) {
            dp[i + 1][j][k] += (1.0 - p[i + 1]) * dp[i][j][k];
            int nxt = min((N << 1), k + a[i + 1]);
            if(nxt >= 0) dp[i + 1][j + 1][nxt] += p[i + 1] * dp[i][j][k];
        }
    }
}

for(int i = l; i <= n; i++) {
    for(int j = N; j <= (N << 1); j++) {
        ans += dp[n][i][j];
    }
}

cpp