1 条题解

  • 0
    @ 2026-11-12 21:57:35

    [J] Sushi(dp_j)题解

    题意简述

    NN 个盘子,第 ii 个有 ai∈{1,2,3}a_i \in \{1,2,3\} 个寿司。每次等概率选一个盘子,有寿司就吃一个。求吃完所有寿司的期望操作次数。

    思路

    状态压缩:只关心"有几盘剩几片"

    关键观察:盘子的编号不重要,只关心还剩 11 片、22 片、33 片的盘子各有多少个。设状态 (i,j,k)(i, j, k) 表示剩 1/2/31/2/3 片的盘子数分别为 i,j,ki, j, k。

    期望方程的推导

    每次操作:

    • 以概率 iN\frac{i}{N} 选到"剩 1 片"的盘子 → 状态变 (i−1,j,k)(i-1, j, k);
    • 以概率 jN\frac{j}{N} → (i+1,j−1,k)(i+1, j-1, k)(剩 2 片的盘子变成剩 1 片);
    • 以概率 kN\frac{k}{N} → (i,j+1,k−1)(i, j+1, k-1);
    • 以概率 N−i−j−kN\frac{N-i-j-k}{N} 选到空盘 → 状态不变(但仍算一次操作)。

    设 f(i,j,k)f(i,j,k) 为从该状态到结束的期望步数,则

    $$f(i,j,k) = 1 + \frac{i}{N} f(i-1,j,k) + \frac{j}{N} f(i+1,j-1,k) + \frac{k}{N} f(i,j+1,k-1) + \frac{N-i-j-k}{N} f(i,j,k).$$

    把右边的 f(i,j,k)f(i,j,k) 移项,两边乘 NN,利用 N−(N−i−j−k)=i+j+kN - (N-i-j-k) = i+j+k:

    $$f(i,j,k) = \frac{N + i\,f(i-1,j,k) + j\,f(i+1,j-1,k) + k\,f(i,j+1,k-1)}{i+j+k}.$$

    这是一条显式递推(不再自引用),可以直接 DP。

    递推顺序与内存

    依赖关系:

    • f(i−1,j,k)f(i-1,j,k):同层 kk、更小 ii ✅(ii 升序已算);
    • f(i+1,j−1,k)f(i+1,j-1,k):同层 kk、更小 jj ✅(jj 升序已算,i+1i+1 虽然更大但那是 j−1j-1 那一轮);
    • f(i,j+1,k−1)f(i,j+1,k-1):上一层 k−1k-1 ✅(kk 升序已算)。

    所以循环按 kk 升序、jj 升序、ii 升序,并只保留 k−1k-1 与 kk 两层。内存 2(N+1)22(N+1)^2 个 double,N=300N=300 时约 1.5 MB。

    答案 f(c1,c2,c3)f(c_1, c_2, c_3)。

    复杂度

    状态数 O(N3)O(N^3),每次 O(1)O(1) 转移,总 O(N3)≤2.7×107O(N^3) \le 2.7\times10^7;时间可接受,空间 O(N2)O(N^2)。

    参考代码

    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    static double cur[305][305], prv[305][305];
    
    int main() {
        int n;
        scanf("%d", &n);
        int c[4] = {0, 0, 0, 0};
        for (int i = 0; i < n; i++) { int a; scanf("%d", &a); c[a]++; }
        for (int k = 0; k <= c[3]; k++) {
            for (int j = 0; j + k <= n; j++) {
                for (int i = 0; i + j + k <= n; i++) {
                    if (i + j + k == 0) { cur[i][j] = 0.0; continue; }
                    double v = n;
                    if (i > 0) v += i * cur[i - 1][j];
                    if (j > 0) v += j * cur[i + 1][j - 1];
                    if (k > 0) v += k * prv[i][j + 1];
                    cur[i][j] = v / (i + j + k);
                }
            }
            memcpy(prv, cur, sizeof(cur));
        }
        printf("%.12f\n", cur[c[1]][c[2]]);
        return 0;
    }
    

    易错点

    1. 不要开 3013301^3 的数组:那是约 218 MB,会 MLE。按 kk 分层只留两层(1.5 MB)。
    2. 转移顺序必须满足"依赖先算":kk 升序 → jj 升序 → ii 升序(ii 用同层更小的、jj 用同层上一轮、kk 用上一层)。
    3. 分母是 i+j+ki+j+k,不是 NN——空盘不贡献进度,但贡献了那一次操作(已体现在分子里的 NN)。
    4. 答案以 c1,c2c_1, c_2 为下标取出:答案状态是"剩 1 片 c1c_1 个、剩 2 片 c2c_2 个、剩 3 片 c3c_3 个(kk 已推进到 c3c_3)"。

    数据说明

    共 19 组:4 组官方样例(含期望 54.4806…54.4806\ldots 的 N=10N=10);N=1N=1 的 a=1/3a=1/3、N=2N=2、全 1/2/31/2/3 的 N=3N=3;N=50/100/300N=50/100/300 随机;N=300N=300 全 11、全 22、全 33 与两类偏分布(最坏 O(N3)O(N^3) 与最大值 c3=300c_3=300)。

    • 1

    信息

    ID
    19
    时间
    2000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者