hdu 1203 I NEED A OFFER!

hdu 1203 I NEED A OFFER!

大家好,又见面了,我是全栈君。

I NEED A OFFER!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 15503    Accepted Submission(s): 6128
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的最大概率,能够转化为求都得不到offer的最小概率。

#include <stdio.h>
#include <iostream>
#include<algorithm>
using namespace std;
#define N 100005
double dp[N];
struct node
{
	int x;
	double y;
}a[N];

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

a:b;}int main(){ int n,m; int k,i,j; while(cin>>n>>m) { if(n==0&&m==0) break; for(i=0;i<m;i++) { cin>>a[i].x>>a[i].y; a[i].y=1-a[i].y; // 得不到offer的概率 } for(i=0;i<=n;i++) dp[i]=1; for(i=0;i<m;i++) { for(j=n;j>=a[i].x;j--) { dp[j]=min(dp[j-a[i].x]*a[i].y,dp[j]); // 要么选这座大学 得不到offer (dp[j-a[i].x]*a[i].y)。要么选这座大学得到offer (dp[j]) } } printf("%.1lf%%\n",(1-dp[n])*100); } return 0;}

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

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

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

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

(0)


相关推荐

  • bootstrap模态框关闭后清除模态框的数据

    bootstrap模态框关闭后清除模态框的数据

  • SpringBootTest用法

    SpringBootTest用法SpringBootTest测试

  • 用AVX2指令集优化浮点数组求和

    用AVX2指令集优化浮点数组求和用AVX2指令集优化浮点数组求和一、AVX2指令集介绍二、代码实现0.数据生成1.普通数组求和2.AVX2指令集求和:单精度浮点(float)3.AVX2指令集求和:双精度浮点(double)三、性能测试测试环境计时方式测试内容进行性能测试第一次测试第二次测试四、总结个人猜测原因:一、AVX2指令集介绍AVX2是SIMD(单指令多数据流)指令集,支持在一个指令周期内同时对256位内存进行操作。包含乘法,加法,位运算等功能。下附Intel官网使用文档。Intel®IntrinsicsGuid

  • Flashfxp 3.4的注册码

    Flashfxp 3.4的注册码FLASHFXP0wC2kbML0wAAAADEW5MNJwTnsl790jgG5F4CTA4jUAdMi66HHqFbShaEpEGXzjtFkAERmtW1wZmK/Vr9KMEMtWcIOXrEECP9avIvc1nfQxdTWr1V4KCB3zPf2djj/s4+66IIFDE2TtaVk88VxI1JlVz+7GX4vCjZhDeN2zwKOnKYnwEHVbXs4S06bzpo7kJ…

  • java 对象拷贝方法beanutils_java copy方法

    java 对象拷贝方法beanutils_java copy方法一、简介:BeanUtils提供对Java反射和自省API的包装。其主要目的是利用反射机制对JavaBean的属性进行处理。我们知道,一个JavaBean通常包含了大量的属性,很多情况下,对JavaBean的处理导致大量get/set代码堆积,增加了代码长度和阅读代码的难度。二、用法:如果你有两个具有很多相同属性的JavaBean,一个很常见的情况…

  • 几个关于silverlight的网站[通俗易懂]

    几个关于silverlight的网站[通俗易懂]1.  示例     http://silverlightnuggets.com/ 2. Silverlight示例    http://silverlight.net/community/communitygallery.aspx 3. http://silverlight.net/Learn/ 

    2022年10月19日

发表回复

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

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