Just another Robbery LightOJ - 1079
题目大意
有$n$家银行,每家银行被抢后抓的概率是$p_{i}$,可获得的金钱是$a_{i}$,问你在被抓几率最高为$P$的情况下可获得的最大金钱数目是多少
解题思路
将危险率转化为安全率,那么即求在安全程度最低为$1-P$的情况下可获得的最大金钱数目,将金钱看成体积,安全程度看成重量,那么问题被转换成为了概率下的01背包问题,$dp[i]$表示在获取金钱数目为$i$时的安全程度,其状态转移方程即为:
AC代码
1 |
|
要是不努力,今天很牛逼,明天很傻逼
有$n$家银行,每家银行被抢后抓的概率是$p_{i}$,可获得的金钱是$a_{i}$,问你在被抓几率最高为$P$的情况下可获得的最大金钱数目是多少
将危险率转化为安全率,那么即求在安全程度最低为$1-P$的情况下可获得的最大金钱数目,将金钱看成体积,安全程度看成重量,那么问题被转换成为了概率下的01背包问题,$dp[i]$表示在获取金钱数目为$i$时的安全程度,其状态转移方程即为:
1 | #include <cmath> |