ATC DP J shushi

ATC DP J shushi

对于$E(d+1,a-1,b,c)$ 其实这个问题中只有三个随机变量，而第一项空盘数是通过其余三项算出来的，所以在推导的时候第一项是没有意义的。

理解了这里就直接照着公式写代码就好了

// dp[i][j][k] 分别表示有1,2,3个寿司的盘子数量
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>using namespace std;
typedef long long ll;
const int N = 400;
const ll MOD = 1e9 + 7;
priority_queue<int> que;int cnt[4];
double dp[N][N][N];
int n;double dfs(int a, int b, int c) {if (a == 0 && b == 0 && c == 0) {return 0;}if (dp[a][b][c] > 0) return dp[a][b][c];double hit = n / (double) (a + b + c);if (a) hit += (1.0 * a / (a + b + c)) * dfs(a - 1, b, c);if (b) hit += (1.0 * b / (a + b + c)) * dfs(a + 1, b - 1, c);if (c) hit += (1.0 * c / (a + b + c)) * dfs(a, b + 1, c - 1);return dp[a][b][c] = hit;}int main() {cin >> n;for (int i = 0; i < n; i++) {int tem;cin >> tem;cnt[tem]++;}double ans = dfs(cnt[1], cnt[2], cnt[3]);printf("%.10f\n", ans);
}