[HDU] 4089 활성화 확률 DP

3572 단어 dpHDU
제목 대의: Tomato가 게임을 하려면 줄을 서야 한다. 처음에 이 대기열은 모두 N명이 있었고 그는 대기열의 M번째 위치에서 유저가 로그인 게임을 활성화할 때마다 확률적으로 네 개의 이벤트를 촉발한다.p1의 확률 등록 실패, 대기열 변화 없음.p2의 확률 연결이 실패하여 팀의 선두에 있는 사람이 팀의 끝까지 줄을 선다.p3의 확률 성공, 팀 첫 출대.p4의 확률 서버 마비, 활성화 정지!이때 토마토 앞에 있는 사람이 K가 모자라면 그는 화가 난다.질문: Tomato가 k위 이내에 있으면 서버가 마비될 확률이 높습니다.
dp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다.
i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1][1] * p2 + p4;
i  >  1 :
2 <= j <= k : dp[i][j] = dp[i][j] * p1 + dp[i][j - 1] * p2 + dp[i - 1][j - 1] * p3 + p4;//앞에 K명이 부족해, 토마토 분노.
k + 1 <= j <= i : dp[i][j] = dp[i][j] * p1 + dp[i][j - 1] * p2 + dp[i - 1][j - 1] * p3;
(여기 k는 i보다 클 수 있습니다. 우리는 잠시 상관하지 않겠습니다. 아래에서 우리는 다시 이곳의 부작용을 없애겠습니다.)
ppp=p2/(1-p1), pp3=p3/(1-p1), pp4=p4/(1-p1);
명령:
i == 1 c[1] = pp4;
2 <= j <= k : c[j] = dp[i - 1][j - 1] * pp3 + pp4;
k + 1 <= j <= i : c[j] = dp[i - 1][j - 1] * pp3;
제거k>i의 경우: 1<=j<=i:c[j]=dp[i-1][j-1]*pp3+(j<=k?pp4:0);(여기 기본 dp[0][j] 초기화됨)
단순화:
j == 1 : dp[i][1] = dp[i][i] * p + c[1]; (1)
2 <= j <= i : dp[i][j] = dp[i][j - 1] * pp2 + c[j];
점차적인 관계에서 알 수 있듯이 dp[i][i]=dp[i][1]*p^(i-1)+tmp;   (2)
그중 tmp=c[1]^(i-1)+c[2]^(i-2)+... + c[i - 1];
연립(1), (2) dp[i][1]를 없애면 dp[i][i] = tmp/(1-p^i);(dp[i][i]도 제거할 수 있음)
회대 득원식: 2<=j최종 해는 dp[n][m]입니다.
코드는 다음과 같습니다.
//HDU 4089 Activation  DP
/*
    p = p2 / (1 - p1)
    p31 = p3 / (1 - p1)
    p41 = p4 / (1 - p1)

    i = 1:           c[1] = pp4, dp[1][1] = pp4 / (1 - p)

             j == 1:c[1] = pp4;
        2 <= j <= k:c[j] = dp[i - 1][j - 1] * pp3 + pp4;(1)
    k + 1 <= j <= i:c[j] = dp[i - 1][j - 1] * pp3;      (2)
     (1)、(2)  :2 <= j <= i:    c[j] = dp[i - 1][j - 1] * pp3 + (i <= k ? pp4 : 0);

     :
             j == 1:dp[i][1] = dp[i][i] * p + c[1];     (3)
        2 <= j <= k:dp[i][j] = dp[i][j - 1] * p + c[j]; (4)
    k + 1 <= j <= i:dp[i][j] = dp[i][j - 1] * p + c[j]; (5)
     (4)、(5)  :2 <= j <= i:    dp[i][j] = dp[i][j - 1] * p + c[j];

      :dp[i][i] = dp[i][1] * pow(p, i - 1) + tmp;   (6)
     tmp = c[1] ^ (i - 1) + c[2] ^ (i - 2) + ... + c[i - 1];
     (3)、(6)  :dp[i][i] = tmp / (1 - pow(p, i));
          :2 <= j <  i:    dp[i][j] = dp[i][j - 1] * p + c[j];

     dp[n][m];
*/

#include <stdio.h>
#include <string.h>
#define REP(i, a, b) for(int i = a; i <= b; ++i)
const double eps = 1e-5;
const int O = 2005;
double pp[O], dp[O][O], c[O], p1, p2, p3, p4, p, pp3, pp4;
int n, m, k;
void work(){
    if(1 - p1 - p2 < eps){// 0 
        printf("%.5f
", 0);
        return;
    }
    if(p4 < eps){// 0.00001 0.00000
        printf("%.5f
", 0);
        return;
    }
    p = p2 / (1 - p1);
    pp3 = p3 / (1 - p1);
    pp4 = p4 / (1 - p1);
    pp[0] = 1.0;
    REP(i, 0, n) dp[0][i] = dp[i][i] = 0;
    REP(i, 1, n) pp[i] = p * pp[i - 1];
    dp[1][1] = p4 / (1 - p1 - p2);
    REP(i, 2, n){
        REP(j, 1, i) c[j] = dp[i - 1][j - 1] * pp3 + (j <= k ? pp4 : 0);
        REP(j, 1, i) dp[i][i] += c[j] * pp[i - j];
        dp[i][i] /= (1 - pp[i]);
        dp[i][1] = dp[i][i] * p + c[1];
        REP(j, 2, i - 1) dp[i][j] = dp[i][j - 1] * p + c[j];
    }
    printf("%.5f
", dp[n][m]);
}
int main(){
    while(~scanf("%d%d%d%lf%lf%lf%lf", &n, &m, &k, &p1, &p2, &p3, &p4)) work();
    return 0;
}
POJ 4089 Activation
HDU-4089 Activation(확률 DP 확률)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage