HDU - 4815 Little Tiger vs. Deep Monkey （长春赛区C题）

题意：有A，B两个人。n道题目。每题有相应的分数。B答对题目的概率是0.5。求A不输给B的概率不小于P要拿的最低分数

思路：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\n", ans);

	}

	return 0;

}