POJ 3028

题目：

有N个牛仔进行决斗，N个人围成一圈依次朝自己选定的人开枪。

每个人存在射击命中率p[i] ，可以选择不开枪。

每个人绝对聪明。

假如存在多种让自己存活概率最大的方案会随机选择一种。

这个过程重复到只剩一个人存活。求每个人存活的概率n<=13

题解：• 定义dp[i][j][k]表示存活状态为i，当前开枪者为j，第k个人的存货概率。 • 直接转移感觉不难。 • 但是不难发现存在一轮所有人都没射中的情况。这种情况一个状态会转移到 自己。 • 假设一个状态转移到自己的概率是p,在有人死亡时状态就会从环中转出，此 时把转出的贡献除以(1-p)即可。 • 剩下的就是复杂的预处理来减少复杂度了。

哪位大佬看懂了写下转移方程⑧