hdu 2955 Robberies 01背包

发布时间:2017-3-29 17:19:47 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 2955 Robberies 01背包",主要涉及到hdu 2955 Robberies 01背包方面的内容,对于hdu 2955 Robberies 01背包感兴趣的同学可以参考一下。

dp[i]代表抢到i的钱且不被抓住的最大概率 1-dp[i]就是被抓住的最小概率 easy~ #include<stdio.h> #include<string.h> double a[110],dp[10010]; int m[110]; double max(double a,double b) { return a>b?a:b; } int main() { int t,i,j,n,k; double P; scanf("%d",&t); while(t--) { scanf("%lf%d",&P,&n); int sum=0; for(i=1;i<=n;i++) { scanf("%d%lf",&m[i],&a[i]); sum+=m[i]; } for(i=0;i<=10010;i++) dp[i]=0.0; dp[0]=1.0; for(i=1;i<=n;i++) { for(j=sum;j>=m[i];j--) { dp[j]=max(dp[j],dp[j-m[i]]*(1-a[i])); } } for(i=sum;i>=0;i--) { if(1.0-dp[i]<=P) { printf("%d\n",i); break; } } } }

上一篇:如何将创作的app发布到苹果…
下一篇:hdu 3033 分组背包 每组至少选一个

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款