hdu 2955 ( Robberies ) 变相01 背包 DP

地址连接：http://acm.hdu.edu.cn/showproblem.php?pid=2955

Roy 去抢N个银行，去抢第j个银行时能得到Mj的钱，被抓的概率为Pj。

问在被抓的概率不大于P时能抢到的最多的钱是多少。

这道题一开始我以为用P去当背包容量，但是P是double型，所以制定不行= =。。然后没大有思路。。。

后来看到网上的思路就是逆向思维，将钱的总数当做背包容量~

于是转成以所有银行的总资产为背包容量V。。求最大的逃跑概率。。

也就是我们一个都不偷的时候我们逃跑的概率为1，每当我们偷了一个我们都要*（1-p[i]）我们成功逃跑的概率

状态转移方程：dp[j] = max ( dp[j], dp[j-cost[i]] * （1-pi[i])..//偷了cost[i]之后，然后就有可能被抓所以要乘以~

代码：

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 int main()
 4 {
 5     int i,n,j,sum,T;
 6     scanf("%d",&T);
 7     while(T--)
 8     {
 9         double p,pi[105],dp[100005];
10         int mon[105];
11         sum = 0;
12         scanf("%lf %d",&p,&n);
13         for(i = 0;i < n;i++)
14         {
15             scanf("%d %lf",&mon[i],&pi[i]);
16             sum+=mon[i];
17         }
18         
19         memset(dp,0,sizeof(dp));
20         dp[0] = 1.0;
21         for(i = 0;i < n;i++)
22         {
23             for(j = sum;j >= mon[i];j--)
24             {
25                 if(dp[j] < dp[j-mon[i]]*(1-pi[i]))
26                 dp[j] = dp[j-mon[i]]*(1-pi[i]);
27 
28             }
29         }
30         for(i = sum;i >= 0;i--)
31         if(dp[i] >= 1-p)
32         break;
33 
34         printf("%d\n",i);
35     }
36     return 0;
37 }