POJ 4089 Activation

제목: N 명이 줄을 서서 계정을 등록하고 팀 머리의 사람만 등록할 수 있지만 서버가 좋지 않으면 다음과 같은 네 가지 상황이 발생한다.
1. 활성화 실패: 이때 줄을 서는 대형은 변하지 않으며 다음 시간을 기다릴 확률은 p1
2. 연결 끊기: 이때 팀의 우두머리는 팀의 끝까지 가서 계속 줄을 선다. 원래 그의 뒤에 있는 사람은 앞으로 이동한다. 확률은 p2이다.
3. 등록 성공: 팀의 우두머리가 뒤의 사람을 떠나 앞으로 이동, 확률은 p3
4. 서버 붕괴: 다들 못 놀 확률은 p4
N명이 줄을 서고 자신이 앞의 k개 위치에서 서버가 붕괴될 확률을 알고 싶습니다.
표시 상태: dp[i][j]는 파티에 i 개인이 있음을 나타냅니다. 이때 자신이 j번째
이동 상황:
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==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끊임없는 교체를 통해 마지막까지 dp[i][i]의 값을 얻을 수 있고 모든 것이 OK~
p4가 너무 작으면 0을 직접 출력할 수 있음을 주의하십시오

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define N 2010
const double eps = 1e-5;
double c[N];
double p[N];
double dp[N][N];


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

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

POJ 2151 Check the difficulty of problems

기본적으로 DP죠. 통계적으로 0이 안 터질 확률을 n문제보다 작고 0이 안 터질 확률을 줄이면 물 건너갈 수 있어요... 이 문제는 경계가 좀 많을 수 있으니 주의해서 쓰시오...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

POJ 4089 Activation

좋은 웹페이지 즐겨찾기