hdu 2955 Robberies 01背包

发布时间:2017-1-19 4:14:24 编辑: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 分组背包 每组至少选一个

相关文章

相关评论