自动搬运

查看原文

来自洛谷，原作者为

	asuldb 哭晕了喵

搬运于2025-08-24 21:31:56，当前版本为作者最后更新于2018-09-05 21:00:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

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

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

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

我决定还是做一做

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

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

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

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

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

之后我们刷表转移

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

于是就有

最后答案就是$\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;
}