首页 > 代码库 > 【hdu2955】 Robberies 01背包
【hdu2955】 Robberies 01背包
hdu2955 http://acm.hdu.edu.cn/showproblem.php?pid=2955
题意:盗贼抢银行,给出n个银行,每个银行有一定的资金和抢劫后被抓的概率,在给定一个概率P,表示盗贼愿意冒险抢劫所能承受的最大被抓概率。
思路:首先用1减去被抓概率,得到安全概率。那抢劫了多家银行后的安全概率就是这些银行各自的安全概率连乘起来。其实是01背包的变种,
dp[j] 表示获得金额 j 时的安全概率。这里用滚动数组,得方程 dp[j] = max(dp[j], dp[i-a[i]]*(1-b[i]) 其中a表示银行金额,b表示被抓概率。
trick:概率的精度不总是2
自WA点: 滚动数组的 j 要逆序遍历。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <vector> 7 #include <map> 8 #include <utility> 9 #include <queue>10 #include <stack>11 #define N 10512 #define REP(i,n) for(i=0;(i)<(n);i++)13 using namespace std;14 const int INF=1<<30;15 const double eps=1e-6;16 17 double dp[N*N],b[N];18 int n,a[N];19 20 void run()21 {22 int _;23 scanf("%d",&_);24 while(_--)25 {26 int sum=0,i,j;27 double p;28 memset(dp,0,sizeof(dp));29 cin>>p>>n;30 REP(i,n)31 {32 cin>>a[i]>>b[i];33 sum+=a[i];34 }35 dp[0]=1.0;36 REP(i,n)37 for(j=sum;j>=a[i];j--)38 {39 dp[j]=max(dp[j],dp[j-a[i]]*(1.0-b[i]));40 }41 for(i=sum;i>=0;i--)42 if(dp[i]>=1.0-p)43 {44 cout<<i<<endl;45 break;46 }47 }48 }49 50 int main()51 {52 // freopen("case.txt","r",stdin);53 run();54 return 0;55 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。