「NOI2005」聪聪与可可-期望dp

给定一个 $n$ 个点, $m$ 条边的无向图。聪聪开始的时候在 S,可可在节点 T 处。以后的每个时间单位,可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 $P$ 个景点与景点 M 相邻,它们分别是景点 R、 景点 S,……,景点 Q,在时刻 $i$ 可可处在景点 M,则在 $i+1$ 时刻,可可有 $\frac{1}{1+P}$ 的可能在景点 R,有 $\frac{1}{1+P}$ 的可能在景点 S,……,有 $\frac{1}{1+P}$ 的可能在景点 Q,还有 $\frac{1}{1+P}$ 的可能停在景点 M

当聪聪在景点 C 时,她会选一个更靠近可可的景点,如果这样的景点有多个,她会选一个标号最小的景点。如果走完第一次移动以后仍然没吃到可可,她还可以在本段时间内再向可可进行一次移动。

在每个时间单位,假设聪聪先走,可可后走。在某一时刻,若聪聪和可可位于同一个景点,则可怜的可可就被吃掉了。

请求出平均情况下,聪聪用几个时间单位就可能吃到可可。

「SCOI2008」奖励关-期望dp

系统将依次随机抛出 $k$ 次宝物,每次你都可以选择吃或者不吃。宝物一共有 $n$ 种,系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。

吃一次第 $i$ 种宝物将得到 $P_i$ 分,但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $S_i$ 。只有当 $S_i$ 中所有宝物都至少吃过一次,才能吃第 $i$ 种宝物。注意,$P_i$ 可以是负数。

假设你采取最优策略,平均情况你一共能在奖励关得到多少分值?

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×