学步园

http://acm.hdu

.edu.cn/showproblem.php?pid=2955

题目大意：有一个小偷要偷银行的钱，可是他偷没家银行总是有一定的概率被抓，现在给了你一个概率P，只要他被抓的概率乘积不大与P，他就是安全的。问你在他安全的情况下，他最多可以偷多少钱。

解题思路：容量为银行钱的总和，价值就是偷到的钱，花费就是被抓的概率。

dp[j] = Max(dp[j],dp[j-w[i]]*(1-p[i]))         dp[j]表示偷到j钱时，他不被抓的概率是多少

#include <stdio.h><br /> #define Max(a,b) a>b?a:b<br /> double dp[10005] = {1};<br /> void Init(int sum)<br /> {<br /> int i;<br /> for(i=1;i<=sum;i++)<br /> dp[i] = 0;<br /> }<br /> struct rob<br /> {<br /> int money;<br /> double p;<br /> }robber[105];<br /> int main()<br /> {<br /> int test,N,i,sum,j;<br /> double P;<br /> scanf("%d",&test);<br /> while (test--)<br /> {<br /> scanf("%lf%d",&P,&N);<br /> for (i=1,sum=0;i<=N;i++)<br /> {<br /> scanf("%d%lf",&robber[i].money,&robber[i].p);<br /> sum+=robber[i].money;<br /> }<br /> Init(sum);<br /> for (i=1;i<=N;i++)<br /> {<br /> for (j=sum;j>=robber[i].money;j--)<br /> dp[j] = Max(dp[j],dp[j-robber[i].money]*(1-robber[i].p));<br /> }<br /> for (i=sum;i>=0;i--)<br /> {<br /> if(dp[i]>=(1-P))<br /> {<br /> printf("%d/n",i);<br /> break;<br /> }<br /> }<br /> }<br /> return 0;<br /> }