题目地址：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}}
$$
\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}}
$$
\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}
$$
\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];
}
}