吃寿司期望(Sushi) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

static double dp[305][305][305];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    int c1 = 0, c2 = 0, c3 = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        if (a == 1) c1++;
        else if (a == 2) c2++;
        else c3++;
    }
    for (int k = 0; k <= n; ++k) {
        for (int j = 0; j + k <= n; ++j) {
            for (int i = 0; i + j + k <= n; ++i) {
                int s = i + j + k;
                if (s == 0) continue;
                double res = (double)n;
                if (i > 0) res += i * dp[i - 1][j][k];
                if (j > 0) res += j * dp[i + 1][j - 1][k];
                if (k > 0) res += k * dp[i][j + 1][k - 1];
                dp[i][j][k] = res / s;
            }
        }
    }
    cout << fixed << setprecision(12) << dp[c1][c2][c3] << "\n";
    return 0;
}