BZOJ P1419 Red is good

题目传送门

思路

状态设计

我们可以想象先把所有牌倒入一个袋子中，然后在一个一个取。
设 $d{p}_{i,j}$ 表示目前袋中有【$i$ 个红牌】和【$j$ 个黑牌】。

状态转移

现在考虑从袋子中抓牌：

1. 抓到的是红牌：
   抓到红牌的概率是 $\frac{i}{i+j}$，抓后袋子中还剩下 $i-1$ 个红牌和 $j$ 个黑牌，那么抓到红牌的期望贡献就是 $\frac{i}{i+j}\times (d{p}_{i-1,j}+1)$；
2. 抓到的是黑牌：
   抓到黑牌的概率是 $\frac{j}{i+j}$，抓后袋子中还剩下 $i$ 个红牌和 $j-1$ 个黑牌，那么抓到红牌的期望贡献就是 $\frac{j}{i+j}\times (d{p}_{i,j-1}+1)$。
3. 随时停止：因为有可以随时停止这一限制，所以在转移时，我们要将 $d{p}_{i,j-1}$ 和 $d{p}_{i-1,j}$ 与 $0$ 取 $max$。因为再在剩下的牌中取时，期望已经是负数，所以取的话肯定更劣。与 $0$ 取 $max$ 就相当于是停止取牌。

因此总得转移方程就是：
$$d{p}_{i,j}=\frac{i}{i+j}\times (max(d{p}_{i-1,j},0)+1)+\frac{j}{i+j}\times (max(d{p}_{i,j-1},0)+1)$$

边界条件

当没有黑牌的时候，$\forall i\in [1,n],d{p}_{i,0}=i$。

复杂度

• 时间复杂度 $O(n\times m)$；
• 空间由于限制了 $64MB$，所以要用滚动数组，最后为 $O(m)$。

代码

#include <bits/stdc++.h>using namespace std;const int maxn = 5e3 + 7;int n, m;
double dp[2][maxn];
int main() {scanf("%d%d", &n, &m);	for (int i = 1; i <= n; ++i) {int now = i & 1, lst = (i - 1) & 1;dp[now][0] = i;for (int j = 1; j <= m; ++j) {dp[now][j] = (max(dp[lst][j], 0.0) + 1) * i / (i + j) + (max(dp[now][j - 1], 0.0) - 1) * j / (i + j);}}int x = dp[n & 1][m] * 1e6;  // 不进位保留 6 位 小数printf("%.6lf\n", max(0.0, x * 1e-6));return 0;
}