CF248E Piglet's Birthday(概率dp)

题面

luogu
CodeForces

题解

\(orz\) yyb

转移蜜罐其实是吓唬人的......
转移的蜜罐都是尝试过的,所有只关心当前架子上的蜜罐数

设\(f[i][j]\)表示第i个货架有j个蜜罐没有被试吃的概率
然后枚举品尝了几个之前没有品尝过的,组合数转移一下

Code

#include<bits/stdc++.h>#define LL long long #define RG registerusing namespace std; template<class T> inline void read(T &x) {x = 0; RG char c = getchar(); bool f = 0;while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();x = f ? -x : x;return ; } template<class T> inline void write(T x) {if (!x) {putchar(48);return ;}if (x < 0) x = -x, putchar('-');int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ; } const int N = 100010; int a[N], b[N]; double f[N][110];inline LL C(int n, int m) {if (n < m) return 0;LL s = 1;for (int i = n; i > n-m; i--) s *= i;for (int i = m; i > 1; i--) s /= i;return s; }int main() {//freopen(".in", "r", stdin);//freopen(".out", "w", stdout);int n, q; read(n);for (int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];double ans = 0;for (int i = 1; i <= n; i++) f[i][a[i]] = 1;for (int i = 1; i <= n; i++) ans += f[i][0];read(q);while (q--) {int u, v, K; read(u); read(v); read(K);ans -= f[u][0];for (int i = 0; i <= a[u]; i++) {double g = 0;LL t = C(b[u], K);for (int k = 0; k <= K; k++) g += f[u][i+k]*C(i+k, k)*C(b[u]-i-k, K-k)*1.0/t;f[u][i] = g;}b[u] -= K; b[v] += K;ans += f[u][0];printf("%.10lf\n", ans);}return 0; }

转载于:https://www.cnblogs.com/zzy2005/p/10220190.html

总结

以上是生活随笔为你收集整理的CF248E Piglet's Birthday(概率dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。