首页 > 代码库 > HDU 4089

HDU 4089

2024-08-03 05:24:09   225人阅读

很容易列出方程

设dp[i][j]为排在第i位置，总共有j个人排队到达目标状态的概率

i=1

dp[i][j]=p4+p1*dp[i][j]+p2*dp[j][j]

2<=i<=k

dp[i][j]=p4+p1*dp[i][j]+p2*dp[i-1][j]+p3*dp[i-1][j-1]

i>k

dp[i][j]=p1*dp[i][j]+p2*dp[i-1][j]+p3*dp[i-1][j-1]

 设p2=p2/(1-p1),p3=p3/(1-p1),p4=p4/(1-p4)

上述三个转移方程化简后为

dp[i][j]=p2*dp[i-1][j]+p3*dp[i-1][j-1]    i>k

dp[i][j]=p4+p2*dp[i-1][j]+p3*dp[i-1][j-1]  2<=i<=k

dp[i][j]=p4+p2*dp[j][j] 　　i==1

 

可以发现同一列的各状态存在一个环的依赖状态，于是，可以先求出dp[j][j]

不妨设dp[i][j]=A[i]*dp[j][j]+B[i]

不停地往上代入，即可得到最终dp[j][j]的表达式了

 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;double p[2050][2050];double A[2050],B[2050];int main(){	int n,m,k,k0,k1;	double p1,p2,p3,p4;	while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF){		if(p4<1e-5){			printf("0.00000\n");			continue;		}	//	cout<<"YES"<<endl;		p[1][1]=p4/(1-p1-p2);		p2=p2/(1-p1); p3=p3/(1-p1); p4=p4/(1-p1);		for(int j=2;j<=n;j++){			for(int i=1;i<=j;i++){				if(i==1){					A[1]=p2; B[1]=p4;				}				else if(i>=2&&i<=k){					A[i]=A[i-1]*p2;					B[i]=p4+p3*p[i-1][j-1]+p2*B[i-1];				}				else{					A[i]=p2*A[i-1];					B[i]=p2*B[i-1]+p3*p[i-1][j-1];				}			}			p[j][j]=B[j]/(1-A[j]);			for(int i=1;i<=j-1;i++){				if(i==1){					p[1][j]=p4+p2*p[j][j];				}				else if(i>=2&&i<=k){					p[i][j]=p4+p2*p[i-1][j]+p3*p[i-1][j-1];				}				else				p[i][j]=p2*p[i-1][j]+p3*p[i-1][j-1];			}		}		printf("%.5lf\n",p[m][n]);	}	return 0;}

　　

HDU 4089


联系
我们