【CF248E】Piglet's Birthday（动态规划）

题面

洛谷

CodeForces

翻译：

给定\(n\)个货架，初始时每个上面有\(a[i]\)个蜜罐。

有\(q\)次操作，每次操作形如\(u,v,k\)，表示从货架\(u\)上任意选择\(k\)个蜜罐试吃（吃过的也还能吃），吃完后把这\(k\)个蜜罐放到\(v\)货架上去。

每次操作完之后回答所有蜜罐都被试吃过的货架数量的期望。

题解

发现没被吃过的数量对于每个货架而言都是单调不增的。

所以考虑没有被吃过的数量，设\(f[i][j]\)表示第\(i\)个货架有\(j\)个蜜罐没有被试吃的概率。

转移的话枚举当前试吃了几个没被吃过的蜜罐用组合数转移即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define MAX 100100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=true,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return t?-x:x;

}

double f[MAX][111],ans;

int n,q,a[MAX],b[MAX];

double C(int n,int m)

{

	if(n<m)return 0;

	double ret=1;

	for(int i=1;i<=m;++i)ret=ret*(1.0*(n-i+1)/i);

	return ret;

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=b[i]=read();

	for(int i=1;i<=n;++i)f[i][a[i]]=1;

	for(int i=1;i<=n;++i)ans+=f[i][0];

	q=read();

	for(int i=1;i<=q;++i)

	{

		int u=read(),v=read(),K=read();ans-=f[u][0];

		for(int j=0;j<=a[u];++j)

		{

			double g=0,tt=C(b[u],K);

			for(int k=0;k<=K;++k)g+=f[u][j+k]*C(j+k,k)*C(b[u]-j-k,K-k)/tt;

			f[u][j]=g;

		}

		b[u]-=K;b[v]+=K;ans+=f[u][0];

		printf("%.10lf\n",ans);

	}

	return 0;

}