HDU-4089 Activation(확률 DP 확률)

2749 단어
제목 대의: 새로운 게임이 계정을 등록할 때 n명의 사용자가 줄을 서 있다.사용자의 정보를 처리할 때마다 다음과 같은 네 가지 상황이 발생할 수 있습니다.
1. 처리 실패, 재처리, 처리 정보는 여전히 대열에 있고 발생 확률은 p1이다.
2. 오류를 처리하고 정보를 처리하여 대열의 끝까지 다시 줄을 서며 발생할 확률은 p2이다.
3. 처리 성공, 팀머리 정보 처리 성공, 출대, 발생 확률은 p3;
4. 서버 고장, 파티의 모든 정보 분실, 발생 확률은 p4;
샤오밍은 현재 팀의 m번째 위치에 있습니다. 앞에 있는 메시지 갯수가 k-1을 초과하지 않을 때 서버가 고장날 확률을 물어봅니다.
제목 분석: 이 문제의 상태 이동 방정식은 쓰기 어렵지 않다.정의 상태 dp(i, j)는 i 개인이 있는 팀에서 그가 j번째 위치에 있을 때 요구 상태에 도달할 확률을 나타낸다.상태 이동 방정식은 다음과 같습니다.
dp(i,1)=p1*dp(i,1)+p2*dp(i,i)+p4
dp(i,j)=p1*dp(i,j)+p2*(i,j-1)+p3*dp(i-1,j-1)+p4  (2<=j<=k)
dp(i,j)=p1*dp(i,j)+p2*(i,j-1)+p3*dp(i-1,j-1)  (k정리하고 p21=p2/(1-p1), p31=p3/(1-p1), p41=p4/(1-p1)를 추가하면 다음과 같은 결과를 얻을 수 있습니다.
dp(i,1)=p21*dp(i,i)+p41
dp(i,j)=p21*dp(i,j-1)+p31*dp(i-1,j-1)+p41  (2<=j<=k)
dp(i,j)=p21*dp(i,j-1)+p31*dp(i-1,j-1)  (k이렇게 하면 추론을 통해 해를 구할 수 있다.
쓰기가 편리하도록 위의 세 개의 이동 방정식을 두 개의 방정식으로 표시한다.
dp(i,1)=p21*dp(i,i)+c(1)
dp(i,j)=p21*dp(i,j-1)+c(j)  (2<=j<=i)
dp(i, i)는 다음을 반복해서 얻을 수 있습니다.
(1-p21^i)dp(i,i)=∑(p21^(i-j))*c(j)  (1<=j<=i)
 
ps: 특판을 해야지, 그렇지 않으면 WA!!!...
 
코드는 다음과 같습니다.
# include<iostream>
# include<cstdio>
# include<cmath>
# include<cstring>
# include<algorithm>
using namespace std;

const double eps=1e-5;

int n,m,k;
double p1,p2,p3,p4;
double dp[2005][2005];

int main()
{
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        scanf("%lf%lf%lf%lf",&p1,&p2,&p3,&p4);
        if(p4<eps){
            printf("0.00000
"); continue; } double p21=p2/(1-p1); double p31=p3/(1-p1); double p41=p4/(1-p1); dp[1][1]=p41/(1-p21); for(int i=2;i<=n;++i){ dp[i][i]=0; for(int j=1;j<=i;++j){ if(j==1) dp[i][i]+=pow(p21,i-j)*p41; else if(j>=2&&j<=k) dp[i][i]+=pow(p21,i-j)*(p31*(dp[i-1][j-1])+p41); else dp[i][i]+=pow(p21,i-j)*p31*dp[i-1][j-1]; } dp[i][i]/=(1-pow(p21,i)); for(int j=1;j<i;++j){ if(j==1) dp[i][j]=p21*dp[i][i]+p41; else if(j>=2&&j<=k) dp[i][j]=p21*dp[i][j-1]+p31*dp[i-1][j-1]+p41; else dp[i][j]=p21*dp[i][j-1]+p31*dp[i-1][j-1]; } } printf("%.5lf
",dp[n][m]); } return 0; }

좋은 웹페이지 즐겨찾기