题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2955
题意：给一个概率p和n个银行，每个银行有一些钱和被抓的概率，问在满足被抓的概率在p以下，抢到的最多的钱是多少
题解：很裸的01背包，不过这里要换成钱的总量当作背包的容量，概率当作价值，维护一个最小的概率
1 #include<cstdio> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 4 double b[110],dp[10010],mx;int t,n,v[110],sum,ans; 5 6 int main(){ 7 scanf("%d",&t); 8 while(t--){ 9 scanf("%lf%d",&mx,&n),sum=0,ans=0; 10 F(i,1,n)scanf("%d%lf",v+i,b+i),sum+=v[i]; 11 F(i,1,sum)dp[i]=1; 12 F(i,1,n)for(int j=sum;j>=v[i];j--){ 13 if(1-(1-dp[j-v[i]])*(1-b[i])<dp[j]) 14 dp[j]=1-(1-dp[j-v[i]])*(1-b[i]); 15 if(dp[j]<mx)ans=ans>j?ans:j; 16 } 17 printf("%d ",ans); 18 } 19 return 0; 20 }