题目概述

有 $n$ 个骰子，每个骰子投出剪刀、石头、布的概率已知。现在每次随机拿出剩余骰子中的一个进行投掷（并不知道这个骰子的概率分布），投完后扔掉。你要出 $n$ 次剪刀石头布，赢了得 $3$ 分，平了得 $1$ 分，输了不得分，求最大期望得分。

解题报告

网上题解讲的都好简略啊（我太菜了）……我翻了一篇英文题解才看懂做法……

根据期望的线性性，我们可以对每次分别求最大贡献，所以我们需要知道第 $i$ 次投 $j$ 这个骰子的概率。

不难发现第 $i​$ 次的概率只和之前投出的剪刀、石头、布的数量有关，所以我们可以定义 $f_{t,i,r,p,s}​$ 表示前 $t​$ 个骰子，第 $i​$ 个骰子还没有用掉，投出了 $r​$ 个石头，$p​$ 个布，$s​$ 个剪刀的概率。

$f_t$ 可以从 $f_{t-1}$ 转移，考虑这次投的是 $t$ 这个骰子，那么需要讨论：

• $i=t$ ：不能投 $t$ ，所以直接继承 $f_{t-1}$ ，概率为 $1-{r+p+s\over t}$ ，即之前没有任何一个投了 $t$ 这个骰子。
• $i\not=t$ ：首先可以继承 $f_{t-1}$ ，然后 $t$ 可能投出剪刀、石头、布，概率为 ${r+p+s\over t}$ 乘上 $t$ 骰子对应的概率。

这样时空复杂度都是 $O(n^5)$ 的，空间凉凉了，但是由于转移是个类似背包的东西，所以可以去掉一维（滚动数组也MLE）。

做完这个之后，我们枚举 $r,p,s$ ，然后枚举这次投出的骰子 $i$ ，计算好概率之后求一下3种情况的最大值就行了。

示例程序

#include<cstdio>
#include<vector>
#define pb push_back
using namespace std;
typedef double DB;
const int maxn=50;

int n;DB a[maxn+5][3],f[maxn+1][maxn+1][maxn+1][maxn+1],ans;

class RockPaperScissors{
public:
    inline DB bestScore(vector<int> R,vector<int> P,vector<int> S){
        for (int i=(n=R.size(),1);i<=n;i++)
            a[i][0]=(DB)R[i-1]/300,a[i][1]=(DB)P[i-1]/300,a[i][2]=(DB)S[i-1]/300;
        for (int i=1;i<=n;i++) f[i][0][0][0]=1;ans=0;
        for (int t=1;t<=n;t++)
            for (int i=1;i<=n;i++)
                for (int r=t;~r;r--)
                    for (int p=t-r;~p;p--)
                        for (int s=t-r-p;~s;s--){
                            DB P=(DB)(r+p+s)/t;f[i][r][p][s]*=1-P;if (i==t) continue;
                            if (r) f[i][r][p][s]+=f[i][r-1][p][s]*P*a[t][0];
                            if (p) f[i][r][p][s]+=f[i][r][p-1][s]*P*a[t][1];
                            if (s) f[i][r][p][s]+=f[i][r][p][s-1]*P*a[t][2];
                        }
        for (int r=0;r<n;r++)
            for (int p=0;p+r<n;p++)
                for (int s=0;r+p+s<n;s++){
                    int num=n-(r+p+s);DB R=0,P=0,S=0;
                    for (int i=1;i<=n;i++){
                        R+=f[i][r][p][s]*a[i][0];
                        P+=f[i][r][p][s]*a[i][1];
                        S+=f[i][r][p][s]*a[i][2];
                    }R/=num;P/=num;S/=num;
                    ans+=max(3*S+R,max(3*R+P,3*P+S));
                }
        return ans;
    }
};