题目链接[http://acm.hdu.edu.cn/showproblem.php?pid=4815]
简单说一下题意:
有n道题,每到题答对得分为a[ i ],假如A不输给B的最小概率是P,那么A最少要得到多少分。
解题过程:
假设有n道题,每个题有两个状态,胜或者败,假设达到某个分数m有k(计数DP)种方式,那么最后是这个分数的概率是k/pow(2,n)。那么A不输给B的概率就是小于等于m的分数的概率和。
#include<bits/stdc++.h>
const int maxn = *;
double dp[maxn];
int a[];
int T,n;
double p;
int main ()
{
scanf("%d",&T);
while(T--)
{
int sum=;
scanf("%d%lf",&n,&p);
for(int i = ;i <= n;i++)
{
scanf("%d",&a[i]);
sum += a[i];
}
for(int i = ;i <= sum;i++)
dp[i]=;
dp[]=;
for(int i = ;i <= n;i++)
for(int j = sum;j >= a[i];j--)
dp[j] += dp[j-a[i]];
double nu = pow(,n);
for(int i = ;i <= sum;i++)
dp[i] /= nu;
double fal = 0.0;
for(int k = ;k <= sum;k++)
{
fal += dp[k];
if(fal >= p)
{
printf("%d\n",k);
break;
}
}
}
return ;
}