TopCoder - 12349 SRM579 Round1 Div1 RockPaperScissors (概率dp)
TopCoder - 12349 SRM579 Round1 Div1 RockPaperScissors (概率dp)
题目大意:
有 \(n\) 个骰子,每个骰子有300个面,其中有 \(a_i,b_i,c_i\) 分别为石头/布/剪刀
每轮你选择出石头/剪刀/布,然后会从剩下的骰子中随机取一个再随机结果,但是你不知道取的是什么骰子
赢一局的权值为3,平局为1
求最优情况下最大的权值期望
\[ \ \]
题目分析:
显然当前的局面只和已经抽出的石头/布/剪刀的数量有关(因为这是你唯一的决策依据,也是唯一影响局面的)
乍一看非常抽象的决策过程,实在无法通过分析得到每一种局面下应该作出的决策
于是考虑能否直接把每一种局面出现的概率求出,决策后将期望线性相加
不妨把随机取出的骰子放在一个序列上,一个局面是由已经出现的骰子和当前第 \(i\) 次决策的骰子组成的
令 \(dp_{i,j,k,typ}\) 表示已经出现的骰子中出现 \(i,j,k\) 个石头/布/剪刀,当前决策时骰子结果为 \(typ\) 的概率
实际在 \(dp\) 时, \(typ\) 一维需要额外加入一个值表示未确定下一个是什么
考虑对于每个骰子,枚举它是已经出现/正在决策/在第 \(i\) 次决策之后出现,将其概率累和
\(dp\) 状态为 \(O(n^3)\) ,转移次数为 \(O(n)\) ,复杂度为 \(O(n^4)\)
最后对于每种局面计算最优的决策即可
1 |
|