测试地址:Activation
题目大意: Tomato要在服务器上激活一个游戏,一开始服务器序列中有
1.有
2.有
3.有
4.有
求Tomato遇到服务器崩溃并且在服务器崩溃时处于前
做法:这一道题是概率DP,而且是一道非常好的题目。
题意比较复杂,但是看到概率,我们就应该想到用DP来求概率。设
当
当
当
注意到有些状态之间是会循环引用的,那是不是就不能用DP来解了呢?不是。事实上,在这些状态中进行概率转移的过程称为马尔可夫过程,而马尔可夫过程平衡的条件是所有状态转移方程被同时满足,我们要求的就是平衡状态下的
于是我们把上列方程化简,方程两侧同减
这样我们就解决了这一题,时间复杂度为
以下是本人代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eps 1e-10
using namespace std;
int n,m,k;
double p1,p2,p3,p4,f[2010][2010];
int main()
{
while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF)
{
if (p4<eps) {printf("0.00000
");continue;}
f[1][1]=p4/(1-p1-p2);
for(int i=2;i<=n;i++)
{
double s1=1,s2=0;
for(int j=2;j<=i;j++)
{
if (j<=k)
{
s1=s1*p2/(1-p1);
s2=(s2*p2+f[i-1][j-1]*p3+p4)/(1-p1);
}
else
{
s1=s1*p2/(1-p1);
s2=(s2*p2+f[i-1][j-1]*p3)/(1-p1);
}
}
s1=1-s1*p2/(1-p1);
s2=(p4+s2*p2)/(1-p1);
f[i][1]=s2/s1;
for(int j=2;j<=i;j++)
{
if (j<=k) f[i][j]=(f[i][j-1]*p2+f[i-1][j-1]*p3+p4)/(1-p1);
else f[i][j]=(f[i][j-1]*p2+f[i-1][j-1]*p3)/(1-p1);
}
}
printf("%.5lf
",f[n][m]);
}
return 0;
}