블 루 브리지 컵 확률 계산
1882 단어 알고리즘
알고리즘 확률 향상 계산
시간 제한:1.0s 메모리 제한:256.0MB
문제 설명
n 개의 8712°[a,b]의 무 작위 정 수 를 생 성하 고 그들의 것 과 x 의 확률 을 출력 합 니 다.
입력 형식
한 줄 에 네 개의 정 수 를 입력 하면 n,a,b,x 순 으로 빈 칸 으로 구분한다.
출력 형식
출력 한 줄 은 작은 숫자 와 x 의 확률 을 포함 하고 소수점 뒤에 네 개의 작은 수 를 유지 합 니 다.
샘플 입력
2 1 3 4
샘플 출력
0.3333
데이터 규모 와 약정
50%의 데이터 에 대하 여 n≤5.
100%의 데이터 에 대하 여 n≤100,b≤100.
분명 한 DP 문제 입 니 다.
직접 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
public class Main
{
static int n, a, b, x;
static int max, min;
static double sum;
static double dp[][], arr[];
static int t;
public static void main(String [] args) throws IOException
{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
a = sc.nextInt();
b = sc.nextInt();
x = sc.nextInt();
t = b-a+1;
sum = Math.pow(t, n);
max = b*n;
min = 1;
arr = new double[t+1];
dp = new double[n+1][max+1];
for(int i = 1, j = a; i <= t; ++i, ++j)
{
arr[i] = j;
}
for(int i = a; i <= b; ++i)
{
dp[1][i] = 1;
}
for(int i = 2; i <= n; ++i)
{
for(int j = 1; j <= t; ++j)
{
for(int k = min; k <= max; ++k)
{
if(dp[i-1][(int) (k-arr[j] <= 0? 0 : k-arr[j])] != 0)
{
dp[i][k] += dp[i-1][(int) (k-arr[j] <= 0? 0 : k-arr[j])];
}
}
}
}
double ans = 1.0*dp[n][x]/sum;
System.out.printf("%.4f", ans);
sc.close();
}
}
숫자 가 너무 커서 더 블 타 입 만 쓸 수 있어 요.구덩이..........................................................
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.