hdu 2955(01 背包)

发布时间:2016-12-7 5:45:07 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 2955(01 背包)",主要涉及到hdu 2955(01 背包)方面的内容,对于hdu 2955(01 背包)感兴趣的同学可以参考一下。

http://acm.hdu.edu.cn/status.php 分析:告诉你Roy不被抓的概率应该大于 P,同时告诉N个银行的存款,和被抓概率;             概率是double型,因而反过来将所有的存款作为01背包的容量;同时需要注意的是被抓概率是不能用于乘法法则的,只有逃跑成功了才能相乘; 代码: #include <iostream> using namespace std; double P; double p[101],f[10001]; //p is probility of escape int m[101]; int main() { int t,n,i,j; int V; cin>>t; while(t--){ cin>>P>>n; V=0; for(i=1;i<=n;i++){ cin>>m[i]>>p[i]; V+=m[i]; } for(i=1;i<=V;i++) f[i]=0; f[0]=1.0; for(i=1;i<=n;i++) for(j=V;j-m[i]>=0;j--) if(f[j]<f[j-m[i]]*(1-p[i])) f[j]=f[j-m[i]]*(1-p[i]); for(i=V;i>=0;i--) if(f[i]-(1-P)>0.000000001){ cout<<i<<endl; break; } } return 0; }

上一篇:1362 循环左移字符串
下一篇:CEdit编辑框透明的实现

相关文章

相关评论