[HDU 4089] Activation[확률 DP]
n명이 줄을 서서 홈페이지에서 게임을 활성화하기를 기다리고 있다.Tomato는 m번째에 랭크되어 있다.대열의 첫 번째 사람에 대해.다음과 같은 상황이 있습니다. 1. 활성화 실패, 대기열에 남아서 다음 활성화(확률은 p1)2를 기다립니다. 연결을 잃고 대기열에서 나온 다음에 대기열의 맨 마지막에 랭크됩니다. (확률은 p2)3. 활성화 성공, 대기열을 떠나는 것(확률은 p3)4. 서버가 마비되고 서버가 활성화를 멈추면 모든 사람이 활성화할 수 없습니다.서버가 다운되었을 때 Tomato가 대기열에 있는 위치<=k의 확률을 구합니다
사고방식: 확률 DP.
사고방식을 찾지 못하는 주요 원인은 dp수조가 도대체 무엇을 나타내는지 잘 모르겠기 때문이다.더 나아가 상태 이동을 적절하게 분석할 수 없다.
확률 DP는 현재 상태에서 최종 상태로 일련의 다중 선택을'봉인'으로 표시하고 최종 결과로 표시한 다음에 제목의 이동 방식에 따라 등호의 좌우 양쪽을 엄격하게 분리한다(항상 자기 순환이 있기 때문에 굳이 구분하지 않으면 혼란스러워진다).식을 다 열거한 후에 어떻게 풀어야 할지 다시 생각해 보자.
dp[i][j]를 설정하면 i 개인이 줄을 서고 Tomato가 j번째 위치에 서서 목표 상태에 도달할 확률(j<=i)dp[n][m]이 바로 구한 j===1:dp[i][1]=p1*dp[i][1]+p2*dp[i][i][i][i]+p2]+p2]+p4를 나타낸다.2<=j<=k: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4; k
참조:http://www.cnblogs.com/kuangbin/archive/2012/10/03/2710987.html
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 2005;
const double EPS = 1e-6;
int m,n,k;
double p1,p2,p3,p4;
double c[MAXN], d[MAXN], a, b, dp[MAXN][MAXN];
int main()
{
while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)==7)
{
if(p4<EPS)
{
printf("0.00000
");
continue;
}
a = p2/(1-p1);
b = p4/(1-p1);
double p31 = p3/(1-p1);
dp[1][1] = b/(1-a);
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
c[j] = p31*dp[i-1][j],d[j] = c[j] + b;
double tmp = 0, exp = 1;
for(int j=i-1;j>0;j--)
{
if(j>=k)
tmp += exp*c[j];
else
tmp += exp*d[j];
exp *= a;
}
tmp += exp*b;
exp *= a;
dp[i][i] = tmp/(1-exp);
dp[i][1] = a*dp[i][i] + b;
for(int j=2;j<i;j++)
{
if(j<=k) dp[i][j] = a*dp[i][j-1] + d[j-1];
else dp[i][j] = a*dp[i][j-1] + c[j-1];
}
}
printf("%.5lf
",dp[n][m]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
