UVA10081 - Tight Words(dp)
제목 링크
제목의 대의: 숫자 [0..k]를 주고 이런 서열을 찾아달라고 한다. 길이는 n이고 서로 인접한 두 숫자 사이의 차이는 1을 넘으면 안 된다.이런 숫자 서열이 나타날 확률을 묻는다.
문제풀이 사고방식: 그동안 이 문제를 거꾸로 생각하다가 서로 인접한 숫자의 차이가 1보다 큰 것을 찾아내려고 했는데 결국 이 문제는 정면으로 생각해야 쓰기 쉽다는 것을 알게 되었다.또 하나는 확률을 직접 계산할 생각은 하지 않고 총 몇 가지를 통계해 총수를 나눈다는 것이다.그 결과 9^100이 너무 커서 큰 숫자를 쓸 뻔했어요...기억화 검색, dp[n][num]: 이미 n번째 수까지 배열되었고 n번째 수가num이면 다음 수는num 또는num-1 또는num+1이다. [1.k]에 부합하면.
코드:
#include <cstdio>
#include <cstring>
const int maxn = 105;
const int maxm = 10;
int K, N;
double p[maxn][maxm];
void init () {
for (int i = 0; i < maxn; i++)
for (int j = 0; j < maxm; j++)
p[i][j] = -1.0;
}
double dp(int n, int k) {
double& ans = p[n][k];
if (ans != -1)
return ans;
if (n == N)
return ans = 1.0;
ans = dp(n + 1, k);
if (k - 1 >= 0)
ans += dp(n + 1, k - 1);
if (k + 1 <= K)
ans += dp(n + 1, k + 1);
ans *= 1.0/(K + 1);
return ans;
}
int main () {
while (scanf ("%d%d", &K, &N) != EOF) {
init();
double ans = 0;
for (int i = 0; i <= K; i++)
ans += dp(1, i);
printf ("%.5lf
", ans * 100.0/(K + 1));
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
