HDU 2955 Robberies（0-1背包）

http://acm.hdu.edu.cn/showproblem.php?pid=2955

题意：一个抢劫犯要去抢劫银行，给出了几家银行的资金和被抓概率，要求在被抓概率不大于给出的被抓概率的情况下，计算出所能抢劫得到的最多资金。

思路：一开始把被抓概率当做背包容量来做，结果错了，很重要的一点就是逃脱概率的计算，不是简单的相加相减，而是在上一家银行抢劫时的逃脱概率再乘以这一次的逃脱概率。

举个例子：

三家银行的被抓概率为P1，P2，P3。那么去抢劫这三家银行的逃脱概率为（1-P1）*(1-P2)*(1-P3)。

我们把银行的资金作为背包容量，状态转移方程为dp[j] = max(dp[j] , dp[j-m[i]] * (1-p[i]))，dp[j]表示在抢劫了j资金之后的最大逃脱概率。

最后我们只需要逆序遍历dp数组，一旦它的逃脱概率大于了给定的逃脱概率，那么此时的i值就是所能得到的最大资金。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int maxn = +;

 int n;

 double dp[maxn];

 double p;

 double pi[maxn];

 int sum;

 int num[maxn];

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int t;

     cin >> t;

     while (t--)

     {

         memset(dp, , sizeof(dp));

         cin >> p >> n;

         sum = ;

         for (int i = ; i <= n; i++)

         {

             cin >> num[i] >> pi[i];

             sum += num[i];

         }

         dp[] = ;   //没抢时逃脱概率为1，这个不能漏

         for (int i = ; i <= n; i++)

         {

             for (int j = sum; j >= num[i]; j--)

                 dp[j] = max(dp[j], dp[j - num[i]] * ( - pi[i]));

         }

         for (int i = sum; i >= ; i--)

         {

             if (dp[i] > ( - p))

             {

                 cout << i << endl;

                 break;

             }

         }

     }

     return ;

 }

巴特西

HDU 2955 Robberies（0-1背包）

最新文章

热门文章