ZOJ3582---Back to the Past
Time Limit: 2 Seconds
Memory Limit: 65536 KB
Special Judge
Recently poet Mr. po encountered a serious problem, rumor said some of his early poems are written by others. This brought a lot of trouble to Mr. po, so one day he went to his best friend MasterO for help. MasterO handed over a small wooden box with a silent smile. Mr. po checked the box, a word "YGBH"carved on the side. "The box can take you back to the past,"MasterO said, "so you can get any evidence you need. But, before that, you need some patience."
There are N tiny dark holes on both sides of the box (2N holes in total). Every day, for each hole, there is a possibility P to successfully absorb the power of moon and then magically sparkle. The possibilities among holes are independent in each day. Once a hole sparkles, it will never turn dark again. The box only works when there are no less than M sparkling holes on each side of the box. The question is that what is the expected number of days before the box is available.
Input
The input consists of several test cases. For each case there are 3 numbers in a line: N, M, P. 1 ≤ N ≤ 50, 1 ≤ M ≤ N, 0.01 ≤ P ≤ 1. A case with three zeros indicates the end of the input.
Output
For each test case, output the expected number of days, accurate up to six decimal places.
Sample Input
2 1 1
1 1 0.5
0 0 0
Sample Output
1.000000
2.666667
Author: ZHENG, Jianqiang
Contest: ZOJ 10th Anniversary Contest
확률 dp, dp[u][v]를 설정하면 첫 번째 면에 u개의 밝은 블랙홀이 있고, 두 번째 면에 v개의 밝은 블랙홀이 있을 때 목표 상태의 기대치에 도달한다.
dp[u][v] = (dp[u + i][v + j] + 1) * C(i, n - u) * (p^i) * ((1-p) ^(n - u - i)) * C(j, n - v) * (p ^ j) & ((1 - p) ^ (n - v - j)) (0 <= i + u <= n && 0 <= j + v <= n )
그리고 살짝 변형해서 i==0 & j===0을 제시하면 점차적으로 미루거나 기억화 검색을 해도 되고 조합수에 대해서는 미리 처리할 수 있습니다.
/*************************************************************************
> File Name: zoj3582.cpp
> Author: ALex
> Mail: [email protected]
> Created Time: 2014 12 25 20 24 54
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
double dp[55][55];
long long C[55][55];
double p, px[55], py[55];
int n, m;
double dfs(int u, int v)
{
if (u >= m && v >= m)
{
return dp[u][v] = 0;
}
if (dp[u][v] != -1)
{
return dp[u][v];
}
double ans = 0;
double p1 = 0, p2 = 0;
for (int i = 0; i + u <= n; ++i)
{
p1 = C[n - u][i] * px[i] * py[n - u - i];
// printf("C[%d][%d] = %lld
", n - u, i, C[n - u][i]);
for (int j = 0; j + v <= n; ++j)
{
if (i == 0 && j == 0)
{
continue;
}
p2 = C[n - v][j] * px[j] * py[n - v - j];
ans += (dfs(u + i, v + j) + 1) * p1 * p2;
}
}
double tmp = py[n - u] * py[n - v];
ans += tmp;
ans /= (1 - tmp);
return dp[u][v] = ans;
}
int main()
{
for (int i = 0; i <= 50; ++i)
{
C[i][0] = 1;
}
C[1][1] = 1;
for (int i = 1; i <= 50; ++i)
{
for (int j = 1; j <= i; ++j)
{
if (i == 1 && j == 1)
{
continue;
}
if (i == j)
{
C[i][j] = 1;
continue;
}
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
while (~scanf("%d%d%lf", &n, &m, &p))
{
if (n == 0 && m == 0 && p == 0)
{
break;
}
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= n; ++j)
{
dp[i][j] = -1.0;
}
}
px[0] = py[0] = 1;
for (int i = 1; i <= n; ++i)
{
px[i] = px[i - 1] * p;
py[i] = py[i - 1] * (1 - p);
// printf("%f %f
", px[i], py[i]);
}
printf("%.6f
", dfs(0, 0));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
수학법칙을 찾으면 돼요. 그다음에 정답은요. k^(m-1)*(n-(m-1)*k)+(m+(m-1)*k+1)*k^(m-1) div 2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.