P7648 [COCI2012-2013#5] MNOGOMET 题解

· · 题解

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

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

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

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

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

其中，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;
}