题意

你要和一堆骰子玩剪刀石头布。有 $n$ 个骰子，每个骰子有三种结果：R，S，P。概率分别是 $pR_i,pS_i,pP_i$。每次你会随机选择一个没有用过的骰子，然后你决定好出什么，然后扔这个骰子。如果获胜得 $3$ 分，平局得 $1$ 分，失败得 $0$ 分。你无法分辨出每一次拿出的骰子是什么，但你可以通过每一局的结果来决策之后的操作。求期望最多可以获得多少得分。

$1 \leq n \leq 50$。

题解

由于玩家可以得到的唯一局面信息是当前骰子出了多少个 RSP。所以我们记录这三个信息 $(i,j,k)$，就可以唯一确定一个局面。

对于一个局面，我们的决策是依赖于当前局面产生 RSP 的概率来计算的。所以我们就需要对于每个 $(i,j,k)$，分别得到下一局产生 RSP 的概率。

考虑如何暴力做这个事情：先枚举哪些骰子是已经使用过的，并且枚举它们的结果。要求结果和 $(i,j,k)$ 相同。然后我们得到了一个概率 $p$，然后将剩下的所有骰子的 $p_r,p_s,p_p$ 都加起来，乘上这个概率 $p$，贡献到答案中。这样最终得到的 R,S,P 的结果在整体中的比例就反应了这个手势出现的概率。

所以我们可以用 dp 做这个事情：设 $g_{a,i,j,k}$ 表示考虑了前 $a$ 个骰子，局面 $(i,j,k)$ 的时候，记录的三种手势的权值。转移枚举当前骰子是否用过，如果用过枚举结果并直接乘上相应的概率；否则我们要把这个权值记录到 $g$ 中，发现直接加不太对，因为我们这个 $g$ 实际上是记录的很多方案的和，每个方案都是一堆系数乘上没有用过的骰子的 $p_r,p_s,p_p$ 的和。所以我们需要同时记录一个系数和就好了。复杂度 $O(n^4)$。

然后就可以直接 dp 算答案了：设 $f_{i,j,k}$ 表示局面是 $(i,j,k)$ 的最优答案，转移枚举这一步出什么，根据 $g$ 算出的概率计算一下期望收益即可。这一部分复杂度 $O(n^3)$。

总复杂度 $O(n^4)$。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 50 + 5;
const DB EPS = 1e-15;

class RockPaperScissors{
private:
    DB r[MAXN],p[MAXN],s[MAXN];int n;
    struct Node{
        DB r,p,s,c;
        Node(DB r=0,DB p=0,DB s=0,DB c=0) : r(r),p(p),s(s),c(c) {}

        Node operator + (const Node &t){
            return Node(r+t.r,p+t.p,s+t.s,c+t.c);
        }

        Node operator * (const DB &t){
            return Node(r*t,p*t,s*t,c*t);
        }
    }g[2][MAXN][MAXN][MAXN];
    // 已经出现 j 个 r,k 个 p,l 个 s,三者出现概率
    DB f[MAXN][MAXN][MAXN];int now;
    bool vis[MAXN][MAXN][MAXN];

    inline DB dp(int i,int j,int k){
        if(i+j+k == n) return 0;
        if(vis[i][j][k]) return f[i][j][k];
        vis[i][j][k] = 1;
        DB &res = f[i][j][k];
        Node t = g[now][i][j][k];
        DB sm = t.r+t.p+t.s;
        if(sm == 0) return res = -1e9;
        t.r /= sm;t.p /= sm;t.s /= sm;
        // 选择 R
        res = t.r*(dp(i+1,j,k)+1)+t.p*(dp(i,j+1,k))+t.s*(dp(i,j,k+1)+3);
        res = std::max(res,t.r*(dp(i+1,j,k)+3)+t.p*(dp(i,j+1,k)+1)+t.s*(dp(i,j,k+1)));
        res = std::max(res,t.r*(dp(i+1,j,k))+t.p*(dp(i,j+1,k)+3)+t.s*(dp(i,j,k+1)+1));
        return res;
    }
public:
    DB bestScore(std::vector<int> _R,std::vector<int> _P,std::vector<int> _S){
        n = SZ(_R);FOR(i,1,n) r[i] = 1.0*_R[i-1]/300,p[i] = 1.0*_P[i-1]/300,s[i] = 1.0*_S[i-1]/300;
        now = 0;CLR(g[now],0);g[now][0][0][0].c = 1;
        FOR(i,1,n){
            CLR(g[now^1],0);
            FOR(j,0,i-1){
                FOR(k,0,i-1-j){
                    FOR(l,0,i-1-j-k){
                        Node t = g[now][j][k][l];
                        g[now^1][j+1][k][l] = g[now^1][j+1][k][l]+(t*r[i]);
                        g[now^1][j][k+1][l] = g[now^1][j][k+1][l]+(t*p[i]);
                        g[now^1][j][k][l+1] = g[now^1][j][k][l+1]+(t*s[i]);
                        g[now^1][j][k][l] = g[now^1][j][k][l]+t+(Node(r[i],p[i],s[i],0)*t.c);
                    }
                }
            }
            now ^= 1;
        }
        return dp(0,0,0);
    }
};