CF248E Piglet's Birthday(概率dp)

题面

题解

\(orz\) yyb

转移蜜罐其实是吓唬人的......

转移的蜜罐都是尝试过的,所有只关心当前架子上的蜜罐数

设\(f[i][j]\)表示第i个货架有j个蜜罐没有被试吃的概率

然后枚举品尝了几个之前没有品尝过的,组合数转移一下

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using 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;

}

巴特西

CF248E Piglet's Birthday(概率dp)

题面

题解

Code

最新文章

热门文章