HDU 4089

很容易列出方程

设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

最新文章

热门文章