hdu 4815 Little Tiger vs. Deep Monkey

概率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 ;

}