题目链接:Problem - D - Codeforces
看了这篇文章来的:【算法学习笔记】概率与期望DP - RioTian - 博客园
这篇博客写得挺好的,讲了一些常见方法,概率 / 期望的题多练练就上手了。
题目大意:
n 个人排队上电梯,每次只有队首那个人可能上电梯,且他上电梯的概率为 p ,一旦上去就不会下来,求 t 秒之后电梯上的人数的期望。
Solution1:
利用期望的定义计算,即 期望 = sum(概率 * 权重) 。
设 表示 i 秒之后电梯上有 j 个人的概率,那么
下面考虑转移方程:
显然
假设当前状态是 ,如果此时 j == n 了,那么转移直接就是
(这一步特判必不可少,因为要满足全概率为 1 的稳定性)
如果 j < n ,则转移取决于此时队首这个人上不上电梯:
上:
不上:
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)。于是问题转化成了计算每条边的期望通过次数。
设想一下,如果我们知道通过每个 "点" 的期望次数,那 "边" 不就迎刃而解了吗?于是问题又转化成了计算每个点的期望通过次数。
设 表示通过状态 (i,j) 这个点的期望次数,那么有:
可以发现其实和 Solution1 如出一辙。
那么对于 "从状态 (i,j) 转移到 (i + 1,j + 1) 的边" 的期望通过次数就是 ,对于 "从状态 (i,j) 转移到 (i + 1,j) 的边" 的期望通过次数就是
。
根据期望的线性性质,总期望等于各边期望贡献之和,即:
(因为我们无需计算边权为0的边的贡献,只算
即可)
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的两种不同思路,适合仔细琢磨。