Sushi 题解
题目传送门
一道 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;
}