hdu 4815 Little Tiger vs. Deep Monkey

时间:2023-03-08 20:19:15

概率dp,有点像背包的做法;

dp[i][j]代表前i个数组成的j数的概率为多少

#include<cstdio>
#include<cstring>
#define maxn 40009
using namespace std; double dp[][maxn];
int s;
double sco; int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
memset(dp,,sizeof dp);
dp[][]=;
scanf("%d%lf",&n,&sco);
for(int i=;i<n;i++)
{
scanf("%d",&s);
for(int j=;j<;j++)
{
dp[i+][j]+=dp[i][j]*0.5;
dp[i+][j+s]+=dp[i][j]*0.5;
}
}
double ans=;
int tmp=;
for(int i=;i<;i++)
{
ans+=dp[n][i];
if(ans>=sco)
{tmp=i;break;}
}
printf("%d\n",tmp);
}
return ;
}