HDU-2955-Robberies-白红宇

HDU-2955-Robberies

阅读量：6712 次

发布时间：2019-06-25

本文共 941 字，大约阅读时间需要 3 分钟。

链接：https://vjudge.net/problem/HDU-2955#author=0

题意：

小偷去抢钱，每个银行有一定的钱和抢这个银行被抓的概率。

被抓概率有一个上限，在不超过这个概率的情况下能抢到的最大的钱是多少。

思路：

将被抓的概率转换为安全的概率。

dp[i] 表示，抢到i的钱的安全概率是多少。

01背包。

代码:

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            using namespace std;typedef long long LL;const int MAXN = 1e4 + 10;double dp[MAXN];int a[MAXN];double b[MAXN];int main(){ int t; int n; double v; scanf("%d", &t); while (t--) { memset(dp, 0, sizeof(dp)); scanf("%lf%d", &v, &n); v = 1 - v; int sum = 0; for (int i = 1;i <= n;i++) { scanf("%d%lf", &a[i], &b[i]); sum += a[i]; b[i] = 1 - b[i];//安全概率 } dp[0] = 1.0; for (int i = 1;i <= n;i++) { for (int j = sum;j >= a[i];j--) dp[j] = max(dp[j], dp[j - a[i]] * b[i]); } for (int i = sum;i >= 0;i--) if (dp[i] >= v) { printf("%d\n", i); break; } } return 0;}