概率/期望 DP llya and Escalator

题目链接：Problem - D - Codeforces

看了这篇文章来的：【算法学习笔记】概率与期望DP - RioTian - 博客园

这篇博客写得挺好的，讲了一些常见方法，概率 / 期望的题多练练就上手了。

题目大意：

n 个人排队上电梯，每次只有队首那个人可能上电梯，且他上电梯的概率为 p ，一旦上去就不会下来，求 t 秒之后电梯上的人数的期望。

Solution1:

利用期望的定义计算，即期望 = sum(概率 * 权重) 。

设 $f_{i,j}$ 表示 i 秒之后电梯上有 j 个人的概率，那么 $Ans = \sum_{i = 0}^{n} f_{t,i} * i$

下面考虑转移方程：

显然 $f_{0,0} = 1.00$

假设当前状态是 $f_{i,j}$ ，如果此时 j == n 了，那么转移直接就是 $f_{i + 1,n} = f_{i,n}$

(这一步特判必不可少，因为要满足全概率为 1 的稳定性)

如果 j < n ，则转移取决于此时队首这个人上不上电梯：

上： $f_{i + 1,j + 1} += p * f_{i,j}$

不上： $f_{i + 1,j} += (1-p) * f_{i,j}$

Code:

#include<cstdio>
#include<cstring>
using namespace std;#define N 2005int n,t;
double p,f[N][N],ans;int main()
{scanf("%d%lf%d",&n,&p,&t);f[0][0] = 1.00,ans = 0.00;for (int i = 0;i < t;++ i){f[i + 1][n] = f[i][n];for (int j = 0;j < n;++ j)f[i + 1][j] += f[i][j] * (1 - p),f[i + 1][j + 1] += f[i][j] * p;}for (int i = 1;i <= n;++ i)ans += i * f[t][i];printf("%.6lf\n",ans);return 0;
}

Solution2:

另一种比较巧妙的技巧，就是把状态抽象成点，把状态之间的转移抽象成边。

定义：只有从状态 (i,j) 转移到 (i + 1,j + 1) 的边的边权为1，从状态 (i,j) 转移到 (i + 1,j) 的边的边权设置为 0 ，那么这里边权的意义就是此次转移增加了电梯上的几个人（1或0）。于是问题转化成了计算每条边的期望通过次数。

设想一下，如果我们知道通过每个 "点" 的期望次数，那 "边" 不就迎刃而解了吗？于是问题又转化成了计算每个点的期望通过次数。

设 $f_{i,j}$ 表示通过状态 (i,j) 这个点的期望次数，那么有：

$f_{i + 1,j + 1} += p * f_{i,j}$

$f_{i + 1,j} += (1-p) * f_{i,j}$

可以发现其实和 Solution1 如出一辙。

那么对于 "从状态 (i,j) 转移到 (i + 1,j + 1) 的边" 的期望通过次数就是 $f_{i,j} * p$ ，对于 "从状态 (i,j) 转移到 (i + 1,j) 的边" 的期望通过次数就是 $f_{i,j} * (1-p)$ 。

根据期望的线性性质，总期望等于各边期望贡献之和，即：

$Ans = \sum_{i = 0}^{t - 1} \sum_{j = 0}^{n - 1} f_{i,j} * p$ （因为我们无需计算边权为0的边的贡献，只算 $f_{i,j} * p$ 即可）

Code:

#include<cstdio>
#include<cstring>
using namespace std;#define N 2005int n,t;
double p,f[N][N],ans;int main()
{scanf("%d%lf%d",&n,&p,&t);f[0][0] = 1.00,ans = 0.00;for (int i = 0;i < t;++ i){f[i + 1][n] += f[i][n];for (int j = 0;j < n;++ j){f[i + 1][j] += f[i][j] * (1.00 - p);f[i + 1][j + 1] += f[i][j] * p;}}for (int i = 0;i < t;++ i)for (int j = 0;j < n;++ j)ans += f[i][j] * p;printf("%.6lf\n",ans);return 0;
}

这两种方法其实体现了期望DP的两种不同思路，适合仔细琢磨。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/diannao/94505.shtml
繁体地址，请注明出处：http://hk.pswp.cn/diannao/94505.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！