直接說題意吧。（什么網友bb了半天題都說不清楚）

給了? P? 表示大于這個概率一定被抓住。則P表示被抓住的概率。N表示現在有的銀行，pi表示被抓的概率嘛。

然后，就看數學了。肯定不能算被抓的概率啊。因為，如果你第一個就被抓了，后面的概率還用算嗎，或則說，這樣的計算不符合01

背包的特點，那么我們就想一下，作為一個背包的容量，應該是做加減法，而不是像概率那樣做乘除啊。那么我們就用銀行的價值作為

物體的體積，而概率（1-被抓的概率=逃跑的概率）作為物品的價值啊。為什么轉化為逃跑的概率呢？因為正面肛不動啊！這樣我們就得到了

價值從小到大的一系列背包啊，不過概率也是遞減的（搶的銀行越多，逃跑的概率越小啊），當我們找到第一個小于（1-P）也是就是他自己的極限逃跑概率時，在之間的價值中找個最大的就可以了

?

?

ac代碼如下：

#include<cstdio> #include<cstring> #define max(a, b) (a)>(b)?(a):(b) #define MAXN int(1e4) double dp[MAXN + 20], p[MAXN]; int w[MAXN]; int main() {int t;scanf("%d", &t);while (t--){memset(dp, 0, sizeof(dp));double pp; int n, v=0;scanf("%lf%d", &pp, &n);for (int i = 1; i <= n; ++i){scanf("%d%lf", &w[i], &p[i]);v += w[i];}dp[0] = 1;for (int i = 1; i <= n; ++i)for (int j = v; j >= w[i]; --j)dp[j] = max(dp[j], dp[j - w[i]] * (1 - p[i]));int maxx = 0;for (int i = 1; i <= v;++i)if (dp[i]>=(1-pp))maxx = max(i, maxx);printf("%d\n", maxx);} }

?

轉載于:https://www.cnblogs.com/ALINGMAOMAO/p/9462921.html

總結

以上是生活随笔為你收集整理的Robberies HDU - 2955的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。