hdu 2955 Robberies
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2955
题意:有一个小偷要偷银行的钱,可是他偷没家银行总是有一定的概率被抓,现在给了你一个概率P,只要他被抓的概率乘积不大与P,他就是安全的。问你在他安全的情况下,他最多可以偷多少钱。
思路:01背包。所有银行的总资产为背包容量V。求最大的逃跑概率。
题目给出被抓的概率,要求最大的逃跑率,即1-p。
状态转移方程:f[j]=max(f[j-mj[i]]*(1-pj[i]),f[j]).
#include <cstdio> #include <cstring> #define max(x,y) ((x)>(y)?(x):(y)) int mj[105]; double p,pj[105],f[10005]; int n,sum; int ZeroOnePack () { int i,j; memset(f,0,sizeof(f)); f[0]=1; for (i=1;i<=n;i++) for (j=sum;j>=mj[i];j--) f[j]=max(f[j-mj[i]]*(1-pj[i]),f[j]); for (i=sum;i>=0;i--) if(f[i]>1-p) return i; } int main () { int T; scanf("%d",&T); while (T--) { sum=0; scanf("%lf%d",&p,&n); for (int i=1;i<=n;i++) { scanf("%d%lf",&mj[i],&pj[i]); sum+=mj[i]; } printf("%d\n",ZeroOnePack ()); } return 0; }
LightOJ 1079 Just another Robbery
题目连接:http://lightoj.com/volume_showproblem.php?problem=1079
和上一题基本一样
#include <cstdio> #include <cstring> #define max(x,y) ((x)>(y)?(x):(y)) int mj[105]; double p,pj[105],f[10005]; int n,sum; int ZeroOnePack () { int i,j; memset(f,0,sizeof(f)); f[0]=1; for (i=1;i<=n;i++) for (j=sum;j>=mj[i];j--) f[j]=max(f[j-mj[i]]*(1-pj[i]),f[j]); for (i=sum;i>=0;i--) if(f[i]>1-p) return i; } int main () { #ifdef ONLINE_JUDGE #else freopen("read.txt","r",stdin); #endif int T; scanf("%d",&T); for (int Cas=1;Cas<=T;Cas++) { sum=0; scanf("%lf%d",&p,&n); for (int i=1;i<=n;i++) { scanf("%d%lf",&mj[i],&pj[i]); sum+=mj[i]; } printf("Case %d: %d\n",Cas,ZeroOnePack ()); } return 0; }