题解：CF167B Wizards and Huge Prize
zzmbj
·
·
题解
CF167B Wizards and Huge Prize
题意
一共 n 场比赛，最开始有一个体积为 k 的背包，每场比赛赢的概率为 p\%，赢一场可能得到一个体积为 1 的奖品（a_i=-1），也可能得到一个容量为 a_i 的背包（a_i\gt 0）。求赢得 l 场比赛并带回所有奖品的概率。
思路
概率 DP。
对于第 $i$ 场可以分为三种情况：
1. 输了，概率为 $1-p_i$。
2. 赢得奖品，需要 $c\gt 0$ 才能装下。
3. 赢得包，容量增加 $a_i$，注意偏移量。
累加所有满足 $j\geqslant l,c\geqslant 0$，$j,c\leqslant n$ 的 $dp_{n,j,c}$ 就是答案。
### 代码
注意 $\max,\min$ 防止 RE。
其实偏移量用什么都可以。
::::info[annotated code]
```cpp line-numbers lines=16,19,20
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n, l, k, c, a[N]; double p[N], dp[N][N][2*N+5], ans; //dp[i][j][c]：前i场，赢j场，当前容量c的概率
int main()
{
ios::sync_with_stdio(); cin.tie();
cin >> n >> l >> k;
for(int i=1; i<=n; i++) {cin >> p[i]; p[i] /= 100.00;}
for(int i=1; i<=n; i++) cin >> a[i];
dp[0][0][min(k,n)+N] = 1.0;
for(int i=1; i<=n; i++) //进行到i
for(int j=0; j<=n; j++) //前i-1场赢了j场
for(int cc=-n; cc<=n; cc++) //i-1场结束后的容量
{c = cc + N;
if(dp[i-1][j][c] == 0) continue; //状态不可达
dp[i][j][c] += dp[i-1][j][c] * (1-p[i]); //输第i场：胜场不变，容量不变，i+1，概率1-p[i]
if(a[i] == -1) dp[i][j+1][max(cc-1, -n) + N] += dp[i-1][j][c] * p[i]; //赢得奖品：胜场+1，容量-1，概率p[i]
else dp[i][j+1][min(cc+a[i], n) + N] += (dp[i-1][j][c] * p[i]); //加包：胜场+1，容量+a[i]
}
for(int j=l; j<=n; j++) //j>=l
for(int c=0; c<=n; c++) //c>=0
ans += dp[n][j][c+N];
printf("%.12lf", ans);
return 0;
}
```
::::
::::success[Accepted code]
> [$\operatorname{submission}$](https://codeforces.com/contest/167/submission/353267445)
::::