Atcoder-dp_j 题解

题目传送门

一道 dp 题……

发现以前课上讲的题能水题解。

在 dp 之前，我们需要明确以下几个东西：

状态的表示，状态转移方程，边界条件跟答案的表示。

状态的表示

$dp_{i,j,k}$ 表示当有 $3$ 个寿司的盘子还剩 $i$ 个，有 $2$ 个寿司的盘子还剩 $j$ 个，有 $1$ 个寿司的盘子还剩 $k$ 个时，吃完所有寿司操作次数的期望。

状态转移方程

当 $i>0$ 时：

$$dp_{i,j,k}=dp_{i,j,k}+dp_{i-1,j+1,k}\times i\div (i+j+k)$$

当 $j>0$ 时：

$$dp_{i,j,k}=dp_{i,j,k}+dp_{i,j-1,k+1}\times j\div (i+j+k)$$

当 $k>0$ 时：

$$dp_{i,j,k}=dp_{i,j,k}+dp_{i,j,k-1}\times k\div (i+j+k)$$

当 $(i+j+k)>0$ 时：

$$dp_{i,j,k}=dp_{i,j,k}+n\div (i+j+k)$$

边界条件

$$dp_{0,0,0}=0$$

答案的表示

$$dp_{cnt_3,cnt_2,cnt_1}$$

其中，$cnt_i$ 表示有 $i$ 个寿司的盘子数量。

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n;
int cnt[4];
double dp[305][305][305];
int main() {
    ios :: sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    for (int i = 0; i <= cnt[3]; i++) {
        for (int j = 0; j <= cnt[2] + cnt[3]; j++) {
            for (int k = 0; k <= cnt[1] + cnt[2] + cnt[3]; k++) {
                if (i == 0 and j == 0 and k == 0) continue;
                if (i > 0) dp[i][j][k] += dp[i - 1][j + 1][k] * i / (i + j + k);
                if (j > 0) dp[i][j][k] += dp[i][j - 1][k + 1] * j / (i + j + k);
                if (k > 0) dp[i][j][k] += dp[i][j][k - 1] * k / (i + j + k);
                dp[i][j][k] += 1.0 * n / (i + j + k);
            }
        }
    }
    printf("%.10lf", dp[cnt[3]][cnt[2]][cnt[1]]);
    return 0;
}