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

思路：DP，dp[i][j]来表示B答了前i题后分数为j的概率，，然后通过B的概率求A的最低分数

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       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; }