问题求解II-HW06 题解
Problem A: 购物
- 令第 $i$ 个人买东西为事件 $E_i$，令恰好有 $r$ 个人买了东西为事件 $E$，已知 $P(E_1),\cdots, P(E_n)$，求 $P(E_1|E),\cdots, P(E_n|E)$。
- $1\leq r\leq n\leq 20$。
方法一：枚举
因为本题数据范围足够小，所以我们可以枚举所有人买或不买的情况，计算出 $P(E)$ 和针对每个人的 $P(E_iE)$，从而根据公式 $P(E_i|E)=P(E_iE)/P(E)$ 得到答案。
方法二：动态规划
考虑如何高效计算 $P(E)$，令 $f(i, j)$ 表示前 $i$ 个人有 $j$ 个购买了东西的概率，那么考虑第 $i$ 个人买不买，有状态转移方程：
$$ f(i, j) = f(i-1, j)\cdot (1-P(E_i)) + f(i-1, j-1)\cdot P(E_i) $$
最后 $f(n, r)$ 即为所求。对于任意一个 $P(E_iE)$，我们只要提前将第 $i$ 个人拎出去，对剩下的 $n-1$ 个人做动态规划，最后 $P(E_i)\cdot f_i(n-1, r-1)$ 即为所求。总时间复杂度 $O(n^3)$。
Problem B: 取数游戏
给定一个长度为 $2n$ 的数列，保证所有数的和是奇数。两个人轮流取数，每次只能取数列的第一个或最后一个数。问双方都采取最优策略的情况下谁能获得胜利。
见 这份题解。