首页 > 代码库 > Activation(hdu 4089)
Activation(hdu 4089)
题目:仙5的激活序列。有以下4种情况:
1、注册失败,但是不影响队列顺序 ,概率为p1
2、连接失败,队首的人排到队尾,概率为p2
3、注册成功,队首离开队列,概率为p3
4、服务器崩溃,激活停止,概率为p4
求主角的位置在K以内,而且服务器崩溃的概率
/* dp[i][j]表示有i个人,主角在j这个位置最后满足要求的概率,dp[n][m]就是所求。 转移方程简单易懂 j==1: dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4; 2<=j<=k: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4; k<j<=i: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]; 化简: j==1: dp[i][1]=p*dp[i][i]+p41; 2<=j<=k: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]+p41; k<j<=i: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]; 其中: p=p2/(1-p1); p31=p3/(1-p1) p41=p4/(1-p1) 然后可以处理出dp[i-1][j-1],这个时候它就相当于常数了 有一个问题是dp[i][i]需要迭代来求(没看懂迭代的部分) */ #include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define N 2010 #define eps 0.000001 using namespace std; int n,m,k; double p1,p2,p3,p4,dp[2005][2005],c[2005],pp[2005]; int main(){ freopen("jh.in","r",stdin); while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF){ if(p4<eps){ printf("0.00000\n"); continue; } double p21=p2/(1-p1); double p31=p3/(1-p1); double p41=p4/(1-p1); pp[0]=1.0; for(int i=1;i<=n;i++) pp[i]=p21*pp[i-1]; dp[1][1]=p4/(1-p1-p2); c[1]=p41; for(int i=2;i<=n;i++){ for(int j=2;j<=k;j++) c[j]=dp[i-1][j-1]*p31+p41; for(int j=k+1;j<=i;j++) c[j]=dp[i-1][j-1]*p31; double tmp=0.0; for(int j=i;j;j--) tmp+=pp[i-j]*c[j]; dp[i][i]=tmp/(1-pp[i]); dp[i][1]=p21*dp[i][i]+p41; for(int j=2;j<i;j++) dp[i][j]=p21*dp[i][j-1]+c[j]; } printf("%.5lf\n",dp[n][m]); } return 0; }
Activation(hdu 4089)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。