HDU-4815 Little Tiger vs.Deep Monkey(長春試合区C題)
999 ワード
A、Bの2人がいて、n道の問題、1題ごとに対応する点数があって、Bは問題に答える確率は0.5で、AがBに負けない確率を求めてPの持つ最低点数より小さくありません
構想:DP,dp[i][j]はBが前のi題に答えた後の点数がjである確率を表し,その後Bの確率でAの最低点数を求める
構想:DP,dp[i][j]はBが前のi題に答えた後の点数がjである確率を表し,その後Bの確率でAの最低点数を求める
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 40010;
int a[MAXN],n;
double P,dp[50][MAXN];
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%lf", &n, &P);
int sum = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j <= sum-a[i]; j++)
if (dp[i][j] > 0) {
dp[i+1][j+a[i]] += dp[i][j]*0.5;
dp[i+1][j] += dp[i][j]*0.5;
}
int ans = 0;
double cnt = 0;
for (int i = 0; i <= sum; i++) {
cnt += dp[n][i];
if (cnt >= P) {
ans = i;
break;
}
}
printf("%d
", ans);
}
return 0;
}