hdu 2955 Robberies 【dp】 01背包

#include<iostream>
using namespace std;
const int maxn=10000+10;
int m[maxn];
double p[maxn],dp[maxn];
int main()
{
    int t,n,sum;
    double p0;
    cin.sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        sum=0;
        cin>>p0>>n;
        for(int i=0;i<n;i++)    cin>>m[i]>>p[i],sum+=m[i];
        for(int i=0;i<n;i++)
            for(int j=sum;j>=m[i];j--)
                dp[j]=max(dp[j],dp[j-m[i]]*(1-p[i]));
        for(int i=sum;i>=0;i--)
            if(dp[i]+p0>1){cout<<i<<endl;break;}
    }
    return 0;
}