zoj 3582 Back to the Past(확률 dp)
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#define B(x) (1<<(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ui;
const int oo = 0x3f3f3f3f;
//const ll OO = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define lson rt<<1
#define rson rt<<1|1
void cmax(int& a, int b){ if (b > a)a = b; }
void cmin(int& a, int b){ if (b < a)a = b; }
void cmax(ll& a, ll b){ if (b > a)a = b; }
void cmin(ll& a, ll b){ if (b < a)a = b; }
void cmax(double& a, double b){ if (a - b < eps) a = b; }
void cmin(double& a, double b){ if (b - a < eps) a = b; }
void add(int& a, int b, int mod){ a = (a + b) % mod; }
void add(ll& a, ll b, ll mod){ a = (a + b) % mod; }
const ll MOD = 1000000007;
const int maxn = 55;
double dp[maxn][maxn];
double C[maxn][maxn];
double p1[maxn], p2[maxn];
void GetC(){
for (int i = 0; i < maxn; i++){
C[i][0] = 1.0;
for (int j = 1; j < i; j++)
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
C[i][i] = 1.0;
}
}
void Init(int n, double p){
p1[0] = 1.0; p2[0] = 1.0;
for (int i = 1; i <= n; i++){
p1[i] = p1[i - 1] * p;
p2[i] = p2[i - 1] * (1.0 - p);
}
}
int main(){
int n, m;
double p;
GetC();
while (scanf("%d %d %lf", &n, &m, &p) != EOF){
if (n == 0 && m == 0)
break;
Init(n, p);
memset(dp, 0, sizeof dp);
for (int i = n; i >= 0; i--)
for (int j = n; j >= 0; j--){
if (i >= m && j >= m)
continue;
for (int x = 0; x + i <= n; x++)
for (int y = 0; y + j <= n; y++){
if (x == 0 && y == 0)
continue;
if (x <= n - i&&y <= n - j)
dp[i][j] += dp[i + x][j + y] * C[n - i][x] * p1[x] * p2[n - x - i] * C[n - j][y] * p1[y] * p2[n - y - j];
}
dp[i][j] = (dp[i][j] + 1.0) / (1.0 - p2[n - i] * p2[n - j]);
}
printf("%.6lf
", dp[0][0]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.