hdu 2895 01背包 Robberies
Robberies
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 24462 Accepted Submission(s): 9037
For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.
His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .
Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.
题目要求的是在不被抓的情况下所能抢的最多的钱。
有小数的是概率,第一个输入的小数是最大的被抓的概率,以后如果抢的被抓的概率大于他的话就会被抓
因为每多抢一家银行就要把被抓的概率相乘,这里用的是不被抓的概率,即如果抢银行不被抓的概率大于我们输入的不被抓的概率那这时就可以成功抢到这笔钱
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#define maxn 105
using namespace std;
double n,b[maxn],dp[];
int a[maxn];
int main()
{
int T;
cin >> T;
while(T--){
int m;
cin >> n >> m;
n = - n;
int sum = ;
for(int i=;i<m;i++){
cin >> a[i] >> b[i];
sum += a[i];
b[i] = - b[i];
}
memset(dp,,sizeof(dp));
dp[] = ;
for(int i=;i<m;i++){
for(int j=sum;j>=a[i];j--){
dp[j] = max(dp[j],dp[j-a[i]]*b[i]);//dp出每一个数的不被抓的概率
}
}
for(int j=sum;j>=;j--){
if(dp[j]-n>1e-){//若不被抓的概率大于题目给出的不被抓的概率,则此时所能抢的金额最多(从最大开始的循环)
cout << j << endl;
break;
}
}
}
return ;
}
最新文章
- iOS阶段学习第20天笔记(MRC内存管理)
- IOS中图片拉伸技巧与方法总结(转载)
- [转]varchar(n),nvarchar(n) 长度、性能、及所占空间分析
- 我的美国(北美)计算机CS实习面试经验分享
- 【LeetCode练习题】Candy
- Javascript之深入浅出prototype
- Java 基本语法----变量
- 关于CDN与缓存(浏览器和CDN)
- 14 python初学(高阶函数 递归函数 内置函数)
- pageObject+selenium
- RS485 VS 20mA 电流环
- selenium自动加载各个浏览器插件
- InvocationHandler和Proxy(Class)的动态代理机制详解
- 双系统Ubuntu无法访问Win10磁盘分区解决方法
- CMake使用总结(转的)+自己的实践心得
- 把url链接转换成二维码的工具类
- Java东西太多,记录一些知识点
- 【SAPUI5】ODataとは
- Es官方文档整理-2.分片内部原理
- Workflow_将一个消息同时发给通过用户(案例)
热门文章
- 2019前端面试系列——HTTP、浏览器面试题
- Apache NiFi 核心概念和关键特性
- React之动画实现
- 使用Jasypt对SpringBoot配置文件加密
- 使用excel计算骰子输赢概率
- 11个rsync使用实例
- (2019版本可用)【idea的安装,激活,设置,卸载】
- hadoop2.7+spark2.2+zookeeper3.4.简单安装
- 【数学+思维】ZZULIOJ 1531: 小L的区间求和
- [HNOI2009]双递增序列(动态规划,序列dp)