POJ 2151 Check the difficulty of problems(확률 DP)

문제의 풀이는 (모든 팀이 최소한 한 문제를 풀 확률-모든 팀이 1에서 N-1 사이를 풀 확률)
DP 상태를 설계할 때 DP 과정에서 어떤 문제를 기록해야 하는지 기록하기 어려우므로 일반적으로 DP의 과정을 방향이 있는 것으로 설계해야 한다. 예를 들어 1차원이 앞의 i개의 XX를 표시하는 등이다.
dp[i][j][k]는 제i팀 앞에서 j문제가 k개를 풀 확률을 나타낸다. dp방정식은 dp[i][j][k]=dp[i][j-1][k-1]*acr[i][j]+dp[i][j-1][k]*(1-acr[i][j]))
dp[i][0][0]를 1로 초기화하고 dp[i][j][0]를 해당 상황에 따라 모든 문제가 틀릴 확률로 설정합니다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
double dp[1005][35][35];
double acr[1005][35];
int M,T,N;
int main(){
	while(~scanf("%d%d%d",&M,&T,&N)){
		if(!M&&!T&&!N) break;
		for(int i=0;i<T;i++){
			for(int j=1;j<=M;j++){
				scanf("%lf",&acr[i][j]);
			}
		}
		
		for(int i=0;i<T;i++){
			dp[i][0][0]=1;
			for(int j=1;j<=M;j++){
				dp[i][j][0]=dp[i][j-1][0]*(1-acr[i][j]);
			}
		}
		for(int i=0;i<T;i++){
			for(int j=1;j<=M;j++){
				for(int k=1;k<=j;k++){
					dp[i][j][k]=dp[i][j-1][k-1]*acr[i][j]+dp[i][j-1][k]*(1-acr[i][j]);
				}
			}
		}
		double tot=1;
		double sub=1;
		for(int i=0;i<T;i++){
			double cur=0;
			for(int j=1;j<=M;j++){
				cur+=dp[i][M][j];
			}
			tot*=cur;
			cur=0;
			for(int j=1;j<N;j++){
				cur+=dp[i][M][j];
			}
			sub*=cur;
		}
		printf("%.3f
",tot-sub);
	}
	return 0;
}

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

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

문제의 풀이는 (모든 팀이 최소한 한 문제를 풀 확률-모든 팀이 1에서 N-1 사이를 풀 확률) DP 상태를 설계할 때 DP 과정에서 어떤 문제를 기록해야 하는지 기록하기 어려우므로 일반적으로 DP의 과정을 방향이 ...

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

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

POJ 2151 Check the difficulty of problems(확률 DP)

좋은 웹페이지 즐겨찾기