杭州电 1203 I NEED A OFFER!

杭州电 1203 I NEED A OFFER!

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

I NEED A OFFER!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15266    Accepted Submission(s): 6031

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。

 

Output
每组数据都相应一个输出,表示Speakless可能得到至少一份offer的最大概率。

用百分数表示,精确到小数点后一位。

 

Sample Input
   
   
10 3 4 0.1 4 0.2 5 0.3 0 0

 

Sample Output
   
   
44.0%
Hint
You should use printf("%%") to print a '%'.

01背包。这里有个小技巧,就是转化为求收不到一份offer的最小概率。

AC代码例如以下:

#include<iostream>
#include<cstdio>
using namespace std;

double min(double a,double b)
{
    return a<b?

a:b;}int main (){ int n,m,a[10005]; int i,j; double b[10005],c[10005],dp[10005]; while(~scanf("%d%d",&n,&m)&&(n||m)) { for(i=1;i<=m;i++) { scanf("%d%lf",&a[i],&b[i]); c[i]=1.0-b[i]; } for(i=0;i<=n;i++) dp[i]=1.0; for(i=1;i<=m;i++) for(j=n;j>=a[i];j--) dp[j]=min(dp[j-a[i]]*c[i],dp[j]); printf("%.1lf%%\n",(1.0-dp[n])*100); } return 0;}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117254.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • dropdown list_css中display中flex

    dropdown list_css中display中flexサンプル画面–>http://ns.adobe.com/mxml/2009″    xmlns:s=”library://ns.adobe.com/flex/spark”    xmlns:mx=”library://ns.adobe.com/flex/mx”    minWidth=”800″    minHeight=”400″>      import

    2022年10月10日
  • 最好的频谱分析仪基础知识「建议收藏」

    最好的频谱分析仪基础知识「建议收藏」转载自网优雇佣军文章目录最好的频谱分析仪基础知识前言有两种技术方法可完成信号频域测量(统称为频谱分析)。快速傅立叶变换频谱分析仪扫频式频谱分析仪工作原理输入衰减器混频器中频滤波器对数放大器检波器视频滤波器扫描本振频谱分析仪关键性能指标频率分辨率相位噪声灵敏度总结一下提高频谱仪测试灵敏度的技术方法:最好的频谱分析仪基础知识前言频谱分析是观察和测量信号幅度和信号失真的一种快速方法,其显示结果可…

  • 中文转拼音【真正的完整版】 拼音 驼峰命名专用

    中文转拼音【真正的完整版】 拼音 驼峰命名专用把下面的代码复制了,在桌面建一个后缀为“.html”格式的文件,如:“拼音.html”,打开 拼音.html,Ctrl+V,Ctrl+S,关闭,再打开&lt;!DOCTYPEhtml&gt;&lt;htmllang="cn"&gt;&lt;head&gt;&lt;metacharset="UTF-8"&gt;&lt;title&gt

  • Java排序算法&nbsp;归并排序

    Java排序算法&nbsp;归并排序

  • 初中英语语法(015)-附加疑问句

    初中英语语法(015)-附加疑问句附加疑问句附加疑问句由陈述句加简短附加问句构成,用以要求对方证实所述之事。附加疑问句主要有两种:一类是反意的附加疑问句,另一类是非反意附加疑问句。例如:1、附加疑问句句尾上升语调,表示询问。(1)YouarefromJapan,aren’tyou?-你来自日本,对吗?AreyoufromJapan?-这句话等同于上句回答方法也相同Yes/No,Iam/I…

  • 一级倒立摆matlab仿真,一级倒立摆的Simulink仿真「建议收藏」

    一级倒立摆matlab仿真,一级倒立摆的Simulink仿真「建议收藏」一级倒立摆的Simulink仿真单级倒立摆稳定控制直线一级倒立摆系统在忽略了空气阻力及各种摩擦之后,可抽象成小车和匀质摆杆组成的系统,如图1所示。mg杆长为2u图1直线一级倒立摆系统图2控制系统结构假设小车质量M=0.5kg,匀质摆杆质量m=0.2kg,摆杆长度2l=0.6m,x(t)为小车的水平位移,θ为摆杆的角位移,。控制的目标是通过外力(t)使得摆直立向上2…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号