定义\(dp[i][j][k]\)是初始情况为：总共有n个盘子，其中 \(i\)个盛有1个寿司的盘子，\(j\)个盛有2个寿司的盘子，\(k\)个盛有3个寿司的盘子 ，在这种初始情况下将寿司全部吃完的期望选择次数
期望选择次数=所有可能出现的选择次数与该选择次数对应的概率相乘，将这些相乘得到的结果相加
i个盛有1个寿司的盘子,j个盛有2个寿司的盘子，k个盛有3个寿司的盘子可能有四种情况的选择次数：
- \(\frac{i}{n}\)的概率选中盛有1个寿司的盘子，然后变成了i-1个盛有1个寿司的盘子，j个盛有两个寿司的盘子，k个盛有3个寿司的盘子。这种情况的选择次数为1+dp[i-1][j][k]（这个数值并不是真的选择次数，而是对dp[i][j][k]的贡献）
- \(\frac{j}{n}\)的概率选中盛有2个寿司的盘子，然后变成了i+1个盛有1个寿司的盘子（盛有两个寿司的盘子，吃掉其中一个寿司，就变成了盛有1个寿司的盘子，所以i->i+1），j-1个盛有两个寿司的盘子，k个盛有3个寿司的盘子。这种情况的选择次数为1+dp[i+1][j-1][k]（同上）
- \(\frac{k}{n}\)的概率选中盛有3个寿司的盘子，然后变成了i个盛有1个寿司的盘子，j+1个盛有两个寿司的盘子，k-1个盛有3个寿司的盘子。这种情况的选择次数为1+dp[i][j+1][k-1]（同上）
- \(\frac{n-i-j-k}{n}\)的概率选中空盘，然后仍然是i个盛有1个寿司的盘子，j个盛有2个寿司的盘子，k个盛有3个寿司的盘子。这种情况的选择次数为1+dp[i][j][k]（同上）
从上面的四种情况的选择次数，根据期望公式可以得到:
\(dp[i][j][k]=\frac{i}{n} (dp[i-1][j][k]+1)+\frac{j}{n}(dp[i+1][j-1][k]+1)+\frac{k}{n}(dp[i][j+1][k-1]+1)+\frac{n-i-j-k}{n}(dp[i][j][k]+1)\)
将公式整理变形可以得到下面的状态转移方程:
\(dp[i][j][k]=\frac{i\times dp[i-1][j][k]+j\times dp[i+1][j-1][k]+k\times dp[i][j+1][k-1]+n}{i+j+k}\)
初始化\(dp[0][0][0]=0\)，意义为初始总共有\(n\)个盘子，没有盘子有寿司，那么不需要选择就已经将寿司全部吃完了，所以选择次数为\(0\)
注意三个循环的关系，由于\(dp[i][j][k]\)依赖于\(dp[i+1][j-1][k]\)，因此\(dp[i+1][j-1][k]\)应该在\(dp[i][j][k]\)之前就被计算过，所以i这个循环应该在j的循环里面，这样在\(j-1\)的时候就计算过\(dp[i+1][j-1][k]\)了.同时\(dp[i][j][k]\)还依赖于\(dp[i][j+1][k-1]\)，所以j循环应该在k循环里面。于是循环从外到内依次为\(k, j, i\)
#include <bits/stdc++.h>
using namespace std;
const int MAXN=305;
//-----------------------
int num[4];
double dp[MAXN][MAXN][MAXN];
int main(void)
{
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++){
int x;
scanf("%d", &x);
num[x]++;
}
dp[0][0][0]=0;
for(int k=0; k<=n; k++){
for(int j=0; j<=n; j++){
for(int i=0; i<=n; i++){
if(i==0 && j==0 && k==0)continue;
if(i)dp[i][j][k]+=i*dp[i-1][j][k];
if(j)dp[i][j][k]+=j*dp[i+1][j-1][k];
if(k)dp[i][j][k]+=k*dp[i][j+1][k-1];
dp[i][j][k]+=n;
dp[i][j][k]/=(double)(i+j+k);
}
}
}
printf("%.20lf\n", dp[num[1]][num[2]][num[3]]);
return 0;
}