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;double dp;//抢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=1;//偷0元钱不被抓的概率肯定为1了，，，for(int i=0;i<n;++i)for(int j=sum;j>=s.a;--j)dp=max(dp,dp.a]*(1-s.b));for(int i=sum;i>=0;--i)if(dp>p){ cout<<i<<endl;break;}}return 0;}
页:
[1]