題目描述

Roy是一個(gè)十分狡猾的家伙，最近他正在計(jì)劃搶劫銀行。為此，他評(píng)估了每家銀行的安全性和每家銀行持有的金錢。但是他知道了自己會(huì)被抓住的最大風(fēng)險(xiǎn)，如果他搶劫銀行被抓的概率小于這個(gè)風(fēng)險(xiǎn)，那他就安全了，否則，他會(huì)被抓走的。Roy并不希望這發(fā)生，因此，他向你求助，他想知道再安全的情況下，能最多搶到多少錢。

輸入

第一行給出一個(gè)整數(shù)T,表示有T組數(shù)據(jù)。

對(duì)于每一組測(cè)試數(shù)據(jù)：

第一行給出一個(gè)浮點(diǎn)數(shù)P，表示Roy允許被抓的最大概率，接著是一個(gè)整數(shù)N，表示他計(jì)劃去搶劫的N個(gè)銀行。

接下來(lái)的N行，每行給出一個(gè)整數(shù)Mi和一個(gè)浮點(diǎn)數(shù)Xi，表示搶劫第i個(gè)銀行可以獲得Mi金錢，被抓走的概率是Xi。

0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mi <= 100
0.0 <= Xi <= 1.0

輸出

對(duì)于每組數(shù)據(jù)，輸出一個(gè)整數(shù)，表示Roy在被抓概率小于P的情況下，能搶到的最多的金錢。

你可以認(rèn)為每家銀行是獨(dú)立的。

樣例輸入

3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05

樣例輸出

2
4
6

分析

• 題目大意是：讓我們求出在被抓概率小于P的情況下獲得的最多金錢。
• 這道題的原型是簡(jiǎn)單的01背包，但是很多人會(huì)誤把被抓的概率當(dāng)成背包容量，把搶到的錢當(dāng)成價(jià)值，然后就gg了。除去被抓概率有可能會(huì)小到小數(shù)點(diǎn)后多少位不說(shuō)（數(shù)組難開(kāi)），被抓的概率也并不像所想的進(jìn)行簡(jiǎn)單的加減就可以得到的。
• 當(dāng)被抓的概率比較難求的時(shí)候，我們不妨考慮它的對(duì)立事件，也就是成功逃跑的概率。只需要在這個(gè)銀行的成功逃跑概率乘于在此之前的成功逃跑概率
  • 現(xiàn)在我們以能打劫的錢的總數(shù)數(shù)作為背包容量，各個(gè)銀行可獲得的錢為所占空間，成功逃跑的概率（用1-被抓的概率可以得到）作為物品價(jià)值。dp[i]則表示打劫了金錢i后的成功逃跑概。即可按照01背包的模型求解。
  • 狀態(tài)轉(zhuǎn)移方程：dp[j]=max(dp[j],dp[j-cash[i]]*pro[i])
  • 最后從后往前遍歷dp[i]數(shù)組，當(dāng)發(fā)現(xiàn)了打劫了金錢i后的成功逃跑概大于或等于允許的最小成功逃跑概率，就把i輸出，結(jié)束循環(huán)。

代碼如下

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int maxn=10000+5,maxs=100+5; int cash[maxs]; int T,n,sum=0; double p,dp[maxn],pro[maxs]; int main() {//freopen("test.txt","r",stdin);cin>>T;while(T--){memset(dp,0,sizeof(dp));sum=0;cin>>p>>n;p=1-p;for(int i=1;i<=n;i++){cin>>cash[i]>>pro[i];pro[i]=1-pro[i];//1-被抓的概率可得成功逃跑的概率sum+=cash[i];//各個(gè)銀行可獲金錢的總和為背包容量}dp[0]=1;//當(dāng)沒(méi)有打劫的時(shí)候，成功逃跑的概率為1for(int i=1;i<=n;i++)for(int j=sum;j>=cash[i];j--)dp[j]=max(dp[j],dp[j-cash[i]]*pro[i]);//狀態(tài)轉(zhuǎn)移方程for(int i=sum;i>=0;i--)if(dp[i]>=p){cout<<i<<endl;break;}}return 0; } 《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的抢劫（01背包+对立事件）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。