HDU - 4815 Little Tiger vs. Deep Monkey
제목의 대의: A, B 두 사람이 있고 n개의 문제가 있는데 매 문제에 대응하는 점수가 있다. B가 문제를 맞힐 확률은 0.5이다. A를 구하면 B에게 지지 않을 확률은 P가 받아야 할 최저 점수보다 적지 않다.
문제풀이 방향:DP,dp[i][j]는 B가 앞의 i문제를 맞힌 후 점수가 j일 확률을 나타낸다. 그리고 B의 확률로 A의 최저 점수를 구한다.
#include <cstdio>
#include <cstring>
double DP[45][40005];
int main() {
int T;
scanf("%d", &T);
while (T--) {
int N, MAX, tmp;
double P;
scanf("%d%lf", &N, &P);
memset(DP, 0, sizeof(DP));
DP[0][0] = 1;
MAX = 0;
for (int i = 0; i < N; i++) {
scanf("%d", &tmp);
for (int j = 0; j <= MAX; j++)
if (DP[i][j] > 0) {
DP[i + 1][j] += DP[i][j] * 0.5;
DP[i + 1][j + tmp] += DP[i][j] * 0.5;
}
MAX += tmp;
}
double sum = 0;
for (int j = 0; j <= MAX; j++) {
sum += DP[N][j];
if (sum >= P) {
printf("%d
", j);
break;
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
