dp #概率期望

\(dp_{i,x,y,z}\) 表示在不使用 \(i\) 的情况下，达到有 \(x\) 个石头，\(y\) 个剪刀，\(z\) 个布的情况的概率

转移可以做背包，每次加入一个

对于每个可能得状态，统计所有可能的下一步的每一个方案的期望，然后取最大值

// Author: xiaruize
#ifndef ONLINE_JUDGE
bool start_of_memory_use;
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 50 + 10;

int n;
double s[N][3];
double dp[N][N][N][N];
double bin[N][N];

void solve()
{
    cin >> n;
    rep(i, 1, n)
    {
        cin >> s[i][0];
        s[i][0] /= 300.0;
    }
    cin >> n;
    rep(i, 1, n)
    {
        cin >> s[i][1];
        s[i][1] /= 300.0;
    }
    cin >> n;
    rep(i, 1, n)
    {
        cin >> s[i][2];
        s[i][2] /= 300.0;
    }
    rep(i, 0, n)
    {
        bin[i][0] = bin[i][i] = 1;
        rep(j, 1, i - 1)
        {
            bin[i][j] = bin[i - 1][j] + bin[i - 1][j - 1];
            cerr << bin[i][j] << ' ';
        }
    }
    rep(i, 1, n)
    {
        dp[i][0][0][0] = 1;
        rep(j, 1, n)
        {
            if (i == j)
                continue;
            per(len, j, 0)
            {
                for (int a = 0; a <= j; a++)
                {
                    for (int b = 0; a + b <= j; b++)
                    {
                        int c = len - a - b;
                        if (a)
                            dp[i][a][b][c] += dp[i][a - 1][b][c] * s[j][0];
                        if (b)
                            dp[i][a][b][c] += dp[i][a][b - 1][c] * s[j][1];
                        if (c)
                            dp[i][a][b][c] += dp[i][a][b][c - 1] * s[j][2];
                    }
                }
            }
        }
        rep(a, 0, n - 1)
        {
            for (int b = 0; a + b < n; b++)
            {
                for (int c = 0; a + b + c < n; c++)
                {
                    dp[i][a][b][c] /= bin[n][a + b + c];
                }
            }
        }
    }
    double res = 0;
    rep(a, 0, n - 1)
    {
        for (int b = 0; a + b < n; b++)
        {
            for (int c = 0; a + b + c < n; c++)
            {
                double x = 0, y = 0, z = 0;
                rep(i, 1, n)
                {
                    x += dp[i][a][b][c] * s[i][0] / (double)(n - a - b - c);
                    y += dp[i][a][b][c] * s[i][1] / (double)(n - a - b - c);
                    z += dp[i][a][b][c] * s[i][2] / (double)(n - a - b - c);
                }
                res += max({x * 3 + y, y * 3 + z, z * 3 + x});
            }
        }
    }
    cout << fixed << setprecision(15) << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}