题意:
给出N道题，和一个概率P，然后给出每道题对应的得分x（每道题只有两个选项，一个正确一个错误）。两个人来答题，一个人是随机选择答案，问另一个人至少要答多少分才能保证有P的概率不会失败。
思路：
01背包，最大分数为40000，01背包处理，记录这40000个分数出现的次数然后从小分数遍历一边即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 40005;
ll dp[maxn], v[45];
int main()
{ll t, n;double p;scanf("%d", &t);while(t--){scanf("%I64d%lf", &n, &p);memset(dp, 0, sizeof(dp));ll sum = 0;for(int i = 1; i <= n; i++){scanf("%I64d", &v[i]);sum += v[i];}dp[0] = 1;for(int i = 1; i <= n; i++)for(int j = sum; j >= v[i]; j--)dp[j] += dp[j-v[i]];ll tmp = 1LL << n;sum = 0;for(int i = 0; i <= 40000; i++){sum += dp[i];if(sum*1.0/tmp >= p){printf("%d\n", i);break;}}}return 0;
}
概率DP写法：
d[i][j]，表示前i道题，得分为j的概率 。 这样，最终打完所有题目之后猴子得任意分数的概率我们就知道了，老虎要想赢就要至少
得和他一样的分数，那么就很好办了，从0~max分，不断相加概率，当概率大于P时的分数就是答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 50;
const double INF = 10000000.0;
int T,n,a[maxn];
double p,d[50][40000+100];
int main()
{scanf("%d",&T);while(T--){scanf("%d%lf",&n,&p);ll sum = 0;for(int i=1; i<=n; i++){scanf("%d",&a[i]);sum += a[i];}memset(d,0,sizeof(d));d[0][0] = 1.0;for(int i=1; i<=n; i++){for(int j=0; j<=sum; j++){if(j >= a[i]) d[i][j] += d[i-1][j-a[i]]/2;d[i][j] += d[i-1][j]/2;}}int ans;double pp = 0.0;for(int i=0; i<=sum; i++){pp += d[n][i];if(pp > p || fabs(pp-p) < 1e-6){ans = i ;break;}}printf("%d\n",ans);}return 0;
}