확률 dp- Ilya and Escalator
제목.
cf518D는 대체적으로 n개인으로 구성된 대기열을 의미한다. 각 단위의 시간에 대기열 헤더는 대기열 확률이 p이거나 대기열을 나가지 않을 수 있다. 확률은 1-p이다. t단위의 시간에 대기열을 나가는 인원수에 대한 기대를 물었다.
사고의 방향
P{X=i}(0<=i<=t)를 계산할 수 있다면 이 문제를 해결할 수 있습니다.정답은
∑i=0nP{X=i}∗i
대상
P{X=i}
dp[i][j]를 설정하면 전 t단위 시간에 j 개인이 대기열에 나올 확률이 있음을 나타낸다.
그러면
dp[i+1][j+1] += dp[i][j] * P
dp[i+1][j] += dp[i][j] * (1 - P)
j>=n일 때 dp[i+1][j]+=dp[i][j]
코드
#include <cstring>
#include <stdio.h>
#include <algorithm>
using namespace std;
int N,T;
double P;
const int maxn = 2010;
double dp[maxn][maxn];
int main() {
scanf("%d%lf%d",&N,&P,&T);
for(int i = 0;i <= T;i ++) {
for(int j = 0;j <= N;j ++) {
dp[i][j] = 0.0;
}
}
dp[0][0] = 1.0;
for(int i = 0;i <= T;i ++) {
for(int j = 0;j <= i;j ++) {
if(j >= N) {
dp[i+1][j] += dp[i][j];
continue;
}
dp[i+1][j+1] += dp[i][j] * P;
dp[i+1][j] += dp[i][j] * (1 - P);
}
}
double ret = 0.0;
for(int i = 1;i <= N;i ++) {
ret += dp[T][i] * i;
}
printf("%f
",ret);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.