题解 P1921 【赌博游戏】

· · 题解

我校最神的金牌爷安利给我的题

金牌爷告诉我这道题水爆了

天啊，金牌爷竟然给我安利题目啦

刚开始看着黑色的标签感觉并不是很可做，但是看到金牌爷脖子上闪闪发光的金牌真挚的眼神

我决定还是做一做

于是就开开心心的做了一道水题

我们设dp[i][j]表示进行到i次游戏，这次游戏使用的是第j个骰子的概率

首先我们先初始化，刚开始第一次游戏能用到的骰子跟\pi(i)有关系

于是dp[1][i]=\pi(i)*a[i][O[1]]

就是选择这个骰子并且能出现这次需要的点数的概率乘起来

之后我们刷表转移

对于一个dp[i][j]我们使用完之后可能会换骰子于是我们就枚举下一个换的骰子k，这个骰子需要出现对应的点数

于是就有

dp[i+1][k]+=dp[i][j]*b[j][k]*a[k][O[i+1]]

最后答案就是\sum_{i=1}^{n}dp[m][i]

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 1005
#define eps 1e-6
#define M 51
double a[M][M],b[M][M];
double pi[M],dp[maxn][maxn];
int O[maxn];
int n,m,Q;
inline int check(double t,double k)
{
    if(t+eps>k&&t-eps<k) return 1;
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    for(re int i=1;i<=n;i++)
        scanf("%lf",&pi[i]);
    for(re int i=1;i<=n;i++)
        for(re int j=0;j<Q;j++)
            scanf("%lf",&a[i][j]);
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=n;j++)
            scanf("%lf",&b[i][j]);
    for(re int i=1;i<=m;i++)
        scanf("%d",&O[i]);
    for(re int i=1;i<=n;i++)
        dp[1][i]=pi[i]*a[i][O[1]];
    for(re int i=1;i<m;i++)
        for(re int j=1;j<=n;j++)
        {
            if(check(dp[i][j],0)) continue;
            for(re int k=1;k<=n;k++)
                dp[i+1][k]+=dp[i][j]*a[k][O[i+1]]*b[j][k];
        }
    double ans=0;
    for(re int i=1;i<=n;i++)
        ans+=dp[m][i];
    printf("%.4lf",ans);
    return 0;
}