HDUJ 1203 I NEED A OFFER!
2024-08-30 16:50:01
I NEED A OFFER!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15669 Accepted Submission(s): 6210
Problem Description
Speakless非常早就想出国,如今他已经考完了全部须要的考试,准备了全部要准备的材料,于是,便须要去申请学校了。要申请国外的不论什么大学。你都要交纳一定的申请费用,这但是非常惊人的。
Speakless没有多少钱,总共仅仅攒了n万美元。他将在m个学校中选择若干的(当然要在他的经济承受范围内)。每一个学校都有不同的申请费用a(万美元)。而且Speakless预计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”,他大叫一声。
帮帮这个可怜的人吧。帮助他计算一下,他能够收到至少一份offer的最大概率。(假设Speakless选择了多个学校,得到随意一个学校的offer都能够)。
Input
输入有若干组数据。每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=10000)
后面的m行,每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。
后面的m行,每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。
Output
每组数据都相应一个输出,表示Speakless可能得到至少一份offer的最大概率。
用百分数表示。精确到小数点后一位。
Sample Input
10 3
4 0.1
4 0.2
5 0.3
0 0
Sample Output
44.0%
#include<iostream>
#include<cstring>
using namespace std; int a[10005];
double b[10005];
double d[10005]; int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
int i,j;
for(i=1;i<=m;i++)
{
scanf("%d%lf",a+i,b+i);
b[i]=1-b[i];
} for(i=0;i<=n;i++)
d[i]=1;
double min=1.1;
for(i=1;i<=m;i++)
{
for(j=n;j>=a[i];j--)
if(d[j]>d[j-a[i]]*b[i])
d[j]=d[j-a[i]]*b[i];
} printf("%.1lf%c\n",(1-d[n])*100,'%');
} return 0;
}
最新文章
- MyBatis基础入门--知识点总结
- sparkR读取csv文件
- Linux服务器管理: 系统的进程管理ps命令
- canvas游戏小试:画一个按方向键移动的圆点
- RDLC系列之三 图片显示
- 再次遇到\r\n转\r问题
- C++采用模板实现栈的方法
- JAVA_build_ant_FixCRLF
- C# DES 加密解密
- ExpandableListView 箭头样式
- xml 和json 数据格式及解析
- ID3算法(2)
- python之路第五篇之递归(进阶篇:续:经典例子剖析)
- 寒假特训——搜索——H - Nephren gives a riddle
- 如何让.net程序支持TLS1.2
- k64 datasheet学习笔记3---Chip Configuration之Human machine interfaces
- python系统编程(九)
- 【OpenFOAM案例】01 elbow
- Java Code Examples for org.codehaus.jackson.map.DeserializationConfig 配置
- 调试kettle插件
热门文章
- [题解] codevs 1486 愚蠢的矿工
- mysql语句中判断是否包含某字符串的方法
- linux shell 自动判断操作系统release 然后连接FTP yum源的脚本
- xfs文件系统修复
- 如何用纯 CSS 绘制一颗闪闪发光的璀璨钻石
- 前端基础之CSS_1
- 图论trainning-part-1 D. Going in Cycle!!
- Archiving not possible: No primary destinations errors
- 单源最短路径 Bellman_ford 和 dijkstra
- 《TCP/IP详解卷1:协议》——第3章 IP:网际协议(转载)