题解：CF2115C Gellyfish and Eternal Violet

违规用户名720023 · 2025-12-15 21:15:29 · 题解

VP rk15 遗憾离场，红温了。私募卡常出题人，但是题很好的。

把数组结构变成这样，操作就可以转化为：

显然上方点等价。

直接对着这个 dp，设 dp_{i, j, k} 表示还剩下 i 次操作，j 层，k 个上方点的概率，最终答案显然是 dp_{0, 1, 0}。转移是简单的，注意 dp_{i - 1, j - 1, n - 1} 可以以 1 - p 的概率转移到 dp_{i, j, 0}。复杂度 nmV^2。

注意到 k 值域 V^2 增大很大复杂度，但是后面一段距离 k 都不会超过 n - 1 所以直接枚举第几次操作将 k 第一次变为 0，这种情况最终达成的概率为 p^{i - k}(1 - p)^k \binom{i - 1}{k - 1}dp_{m - i, \max(j - (i - k), 1), 0}。

直接按着式子实现即可。

本题卡精度卡常。提高精度和常数的做法见代码。

#include <iostream>
#include <cstring>
using namespace std;
int n, m, pp;
double dp[4010][410][30], g[16010];
int h[30];
double p;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    for(int i = 0; i <= 4000; i++) dp[i][1][0] = 1;
    while(T--) {
        cin >> n >> m >> pp;
        p = pp * 1.0 / 100;
        int sk = 0, smn = 0x3f3f3f3f;
        for(int i = 1; i <= n; i++) cin >> h[i], smn = min(smn, h[i]);
        for(int i = 1; i <= n; i++) sk += h[i] - smn;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= smn; j++){
                if(j != 1) dp[i][j][0] = p * dp[i - 1][j - 1][0] + (1 - p) * max(dp[i - 1][j - 1][n - 1], dp[i - 1][j][0]);
                for(int k = 1; k < n; k++) dp[i][j][k] = p * dp[i - 1][j - (j != 1)][k] + (1 - p) * dp[i - 1][j][k - 1];
            }
        }
        if(sk < n){
            cout << dp[m][smn][sk] << '\n';
            continue;
        }
        double ans = 0;
        for(int i = 1; i <= sk + 1; i++) g[i] = 0;
        g[sk] = 1;
        for(int i = 1; i <= m; i++) {
            //cerr << g[1] << '\n';
            ans += (1 - p) * g[1] * dp[m - i][max(smn - (i - sk), 1)][0];
            for(int j = 1; j <= sk; j++) g[j] = p * g[j] + (1 - p) * g[j + 1];
        }
        cout << ans << '\n';
    }
    return 0;
}

过了就 rk1 了。