自动搬运

查看原文

来自洛谷，原作者为

	Kelvin2009 Never gonna give you up.

搬运于2025-08-24 22:31:52，当前版本为作者最后更新于2024-08-20 22:47:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是一道期望 dp 加状态优化。

枚举此时球在哪个队员手上且双方的得分情况显然不行，时间复杂度危险。

注意到进球情况并不主要依赖于时间的推移，考虑设定新的状态 $dp_{i,a,b,id}$ 表示在时刻 $i$，0 队得 $a$ 分，1 队得 $b$ 分，某队恰好刚进球，此时球权将交给 $id$ 队 1 号队员。

对于 $id$ 队的队员 $m$，默认其在球场上的编号为 $id\cdotp n+m$。

考虑如何转移，首先要维护 3 种概率：

1. $hold_{id,con,j}$ 表示从 $id$ 队开始，传了 $con$ 次，中途没有进球，传到了球员 $j$ 手上的概率（不管是主观传还是被抢，只看作一种可能得状态）。

2. $goal_{a,b,con}$ 表示从 $a$ 队发球，传了 $con$ 次后由 $b$ 队第一次进球的概率。

3. $sum_{a,con}$ 表示从 $a$ 队发球，传了不超过 $con$ 次新进了球的概率。

其中，$hold_{id,con,j}$ 与 $goal_{a,b,con}$ 可以通过刷表求得，而 $sum_{a,con}$ 则是 $goal_{a,b,con}$ 的前缀和。

即：

$$sum_{a,con}=goal_{a,a,0}+\displaystyle\sum_{i=1}^{con}(goal_{a,0,i}+goal_{a,1,i}) $$

然后 $dp_{i,a,b,id}$ 就可通过刷表求得。

若最终 0 队得 $a$ 分，1 队得 $b$ 分，令该方案数为 $ans_{a,b}$。

具体的：

$$ans_{a,b}=\displaystyle\sum_{i=0}^{T}\displaystyle\sum_{id=0}^{1}(1-sum_{id,T-i})\cdot dp_{i,a,b,id} $$

---

代码：

---

#include<bits/stdc++.h>
using namespace std;
const int rrange=15;
const int vrange=205;
const int trange=505;
const int erange=4e4+5;

int n,r,t;

//ho[a][i][j]:P（a队开球，转i次后球未进，在j号球员手上）
//go[a][b][i]:P（a队开球，第一次进球为转i次后b队进)
//sum[a][i]:P（a队开球，转不超过i次后进一球）
//dp[i][a][b][j]:P（球经过i次进球，比分为a（0队）:b（1队）,球在j队1号手上）
//ans[a][b]:P（最终比分为a（0队）:b（1队））

double p[vrange],val[vrange];

double ho[2][trange][vrange];
double go[2][2][trange],sum[2][trange];
double dp[trange][rrange][rrange][2],ans[rrange][rrange];

int cnt=1,to[erange],nxt[erange],head[vrange];

inline void add(int u,int v)
{
	cnt++;
	nxt[cnt]=head[u];
	to[cnt]=v;
	head[u]=cnt;
}

int main()
{
	scanf("%d%d%d",&n,&r,&t);
	for(int id=0;id<2;id++)
	{
		for(int m=1;m<=n;m++)
		{
			int nf,ne,v;
			int u=id*n+m;
			scanf("%lf%d%d",&p[u],&nf,&ne);
			for(int i=1;i<=nf;i++)
			{
				scanf("%d",&v);
				v=id*n+v;add(u,v);
			}
			for(int i=1;i<=ne;i++)
			{
				scanf("%d",&v);
				v=(1-id)*n+v;add(u,v);
			}
			val[u]=1.0/(nf+ne+1);
		}
	}
	for(int id=0;id<2;id++)
	{
		int beg=id*n+1;
		ho[id][0][beg]=1.0;
		int tran=t-id;
		for(int con=0;con<=tran;con++)
		{
			int ran=2*n;
			for(int u=1;u<=ran;u++)
			{
				if(ho[id][con][u]==0.0) continue;
				for(int i=head[u];i;i=nxt[i])
				{
					int v=to[i];
					ho[id][con+1][v]+=ho[id][con][u]*val[u];
				}
				ho[id][con+1][(u<=n)*n+1]+=ho[id][con][u]*val[u]*(1-p[u]);
				go[id][(u>n)][con+1]+=ho[id][con][u]*val[u]*p[u];
			}
		}
		sum[id][0]=go[id][id][0];
		for(int con=1;con<=tran;con++)
		{
			sum[id][con]=go[id][0][con]+go[id][1][con];
			sum[id][con]+=sum[id][con-1];
		}
	}
	dp[0][0][0][0]=1.0;
	for(int con=0;con<=t;con++)
	{
		for(int a=0;a<=r;a++)
		{
			for(int b=0;b<=r;b++)
			{
				for(int id=0;id<2;id++)
				{
					if(dp[con][a][b][id]==0.0) continue;
					if(a==r || b==r || con==t)
					{
						ans[a][b]+=dp[con][a][b][id];
						continue;
					}
					int ran=t-con;
					for(int res=1;res<=ran;res++)
					{
						dp[con+res][a+1][b][1]+=dp[con][a][b][id]*go[id][0][res];
						dp[con+res][a][b+1][0]+=dp[con][a][b][id]*go[id][1][res];
					}
					ans[a][b]+=dp[con][a][b][id]*(1.0-sum[id][t-con]);
				}
			}
		}
	}
	int ran=r*(r+2);
	for(int i=0;i<ran;i++) printf("%.7lf\n",ans[i/(r+1)][i%(r+1)]);
	return 0;
}