Robberies&&http://acm.hdu.edu.cn/showproblem.php?pid=2955

江湖浪人

　　http://acm.hdu.edu.cn/showproblem.php?pid=2955
　　这一题算是0-1背包的变种，，通过构造背包，，来求在满足情况的条件下，背包的最大容量。。。
　　思路：题目给出我们被抓的最大概率。即给出不被抓的最小概率，因此我们可以构造dp来存不被抓的最大概率。。以所有银行的钱为背包容量，以（1-p）表示背包的价值，从而求对应背包的最大价值。。。。
#include<iostream>#include<string.h>#include<algorithm>using namespace std;typedef struct{   int a;double b;}Node;Node s[101];double dp[10001];//抢i元不被抓的最大概率 int main(){ int Case;cin>>Case;while(Case--){ int n;double p;cin>>p>>n;p=1-p;  //不被抓的最小概率 int sum=0;memset(dp,0,sizeof(dp));for(int i=0;i!=n;++i){cin>>s.a>>s.b;sum+=s.a;}dp[0]=1;//偷0元钱不被抓的概率肯定为1了，，，for(int i=0;i<n;++i)for(int j=sum;j>=s.a;--j)dp[j]=max(dp[j],dp[j-s.a]*(1-s.b));for(int i=sum;i>=0;--i)if(dp>p){ cout<<i<<endl;break;}}return 0;}