RockPaperScissors

作者：闫书弈

关键词：期望动态规划

题目简述

在一个袋子里有n个骰子，每个骰子有300面，第i个骰子ai面上有石头，bi面上有布，ci面上有骰子。

游戏持续n轮，每一轮你需要从石头、剪刀、布中选择一个，然后从袋子中等概率随机取出一个骰子，并滚动它来产生你对手的手势。接着这个骰子会被扔掉。

注意，你只知道这次滚动的结果，却不知道取出的骰子是哪一个。

每一轮胜利获得3分，平局获得1分，失败不得分。

你需要求出最优策略下你的期望得分。

n<=50，0<=ai,bi,ci<=300，ai+bi+ci=300。

由期望的性质可知，可以分别处理每一轮的期望得分。

显然，我们某一轮的策略只与之前对手出现过的三种手势的数量有关。

我们用f[i][j][k][0]表示前i+j+k轮出现i个石头，j个剪刀，k个布的概率；用f[i][j][k][l]表示前i+j+k轮出现i个石头，j个剪刀，k个布，且第i+j+k+1轮出现l的概率(1,2,3分别表示石头、剪刀、布)。

dp时加入一维u，表示当前处理了前u个骰子。转移时枚举当前骰子是前若干轮出现的石头/剪刀/布，或者是下一轮出现的石头/剪刀/布，或者都不是。

求出f以后，这一轮出石头的期望得分就是(3*f[i][j][k][1]+f[i][j][k][2])/f[i][j][k][0]，剪刀和布也类似。枚举所有i,j,k，将这个式子求和，然后从三个手势中选取一个最优的即可。