首页 > 代码库 > （背包dp）HDU - 2955 Robberies

（背包dp）HDU - 2955 Robberies

2024-08-11 17:17:29   220人阅读

原题链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=2955

（可能失效）

题意：小偷抢劫n个银行，每个银行有两个属性，m为拥有的库存金额，p为小偷偷这个银行被抓的概率。小偷抢银行的总被抓概率不能超过V。求最多抢到的金额。

分析：这题拿到手很容易想到把概率*100，以总概率V为背包容积，以抢到的金额为价值跑01背包。

但是确实本题坑之所在。WA了好多发。

看了大神博客才明白，这里需要一个转化，直接跑以总金额sum为容积，不被抓的概率为价值的背包，最后一波循环求出所得金额最大，1-不被抓概率>=总被抓的概率V就行了。

注意点：求不被抓的概率时候要*，而不是+，之前很智障的写了个+。。因为要*，需要处理边界，dp[0]=1。

代码：

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<set> 7 #include<vector> 8 #include<queue> 9 #include<map>10 #include<list>11 #include<bitset>12 #include<string>13 #include<cctype>14 #include<cstdlib>15 16 using namespace std;17 18 typedef long long ll;19 typedef unsigned long long ull;20 21 int t;22 double V;23 int n;24 const int maxn=10010;25 double v[110];26 int m[100];27 double dp[maxn];28 29 void solve() {30     scanf("%d",&t);31     while(t--){32         memset(dp,0,sizeof(dp));33         scanf("%lf%d",&V,&n);34         int sum=0;35         for(int i=0;i<n;i++){36             scanf("%d%lf",&m[i],&v[i]);37             sum+=m[i];38         }39         dp[0]=1;40         for(int i=0;i<n;i++){41             for(int j=sum;j>=m[i];j--){42                 dp[j]=max(dp[j],dp[j-m[i]]*(1-v[i]));43             }44         }45         int i;46         for(i=sum;1-dp[i]>=V;i--);47         printf("%d\n",i);48     }49 }50 51 52 53 int main() {54 55 #ifndef ONLINE_JUDGE56     freopen("in.txt", "r", stdin);57     //freopen("out.txt", "w", stdout);58 #endif59     //iostream::sync_with_stdio(false);60     solve();61     return 0;62 }

 

（背包dp）HDU - 2955 Robberies


联系
我们