哪个网站上网好,网站模块数据同步,网站建设安全方案,重庆最新通告题目#xff1a;
蒜头君很早就想出国#xff0c;现在他已经考完了所有需要的考试#xff0c;准备了所有要准备的材料#xff0c;于是#xff0c;便需要去申请学校了。要申请国外的任何大学#xff0c;你都要交纳一定的申请费用#xff0c;这可是很惊人的。蒜头君没有多…题目
蒜头君很早就想出国现在他已经考完了所有需要的考试准备了所有要准备的材料于是便需要去申请学校了。要申请国外的任何大学你都要交纳一定的申请费用这可是很惊人的。蒜头君没有多少钱总共只攒了 n 万美元。他将在 m 个学校中选择若干的当然要在他的经济承受范围内。每个学校都有不同的申请费用a万美元并且蒜头君估计了他得到这个学校 offer 的可能性 b。
不同学校之间是否得到 offer 不会互相影响。“I NEED A OFFER”他大叫一声。帮帮这个可怜的人吧帮助他计算一下他可以收到至少一份offer的最大概率。如果蒜头君选择了多个学校得到任意一个学校的offer都可以。
输入格式
第一行有两个正整数 n,m(0≤n≤10000,0≤m≤10000)n,m(0 \le n \le 10000,0 \le m \le 10000)n,m(0≤n≤10000,0≤m≤10000)。
后面的 m 行每行都有两个数据 aia_iai(整型), bib_ibi (实型)分别表示第 i 个学校的申请费用和可能拿到 offer 的概率。
输出格式
每组数据都对应一个输出表示蒜头君可能得到至少一份 offer 的最大概率。用百分数表示精确到小数点后一位。
输出时每行末尾的多余空格不影响答案正确性
要求使用「文件输入输出」的方式解题输入文件为 offer.in输出文件为 offer.out
样例输入
10 3 4 0.1 4 0.2 5 0.3
样例输出
44.0%
分析
当看见01背包问题的模型有 n个物品和一个容量为 W 的背包每个物品有重量 wiw_{i}wi 和价值viv_{i}vi两种属性要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。)再考虑如何将某offer放入dp[j]表示花费j元至少可以拿到一个学校的offer的概率。当有一所学校是花费x元拿到offer的概率是y。所以这个时候就是1.0-(1- dp[j-x])*(1-y)先计算一 个都考不上的概率,然后它的补集即是至少可以考上一个学校的概率。状态转移方程: dp[j]max(dp[j],1.0−(1−dp[j−x])∗(1−y))dp[j] max(dp[j],1.0-(1- dp[j-x])*(1- y))dp[j]max(dp[j],1.0−(1−dp[j−x])∗(1−y))
AC代码
#includestdio.h
#includestring.h
#includealgorithm
#includeiostream
using namespace std;
const int M1e410;
const int inf0x3f3f3f3f;
double dp[M],b[M];
int a[M];
int n,m;
int main(){freopen(offer.in, r, stdin);freopen(offer.out, w, stdout);cinnm;for(int i0;im;i)cina[i]b[i];for(int i0;im;i)for(int jn;ja[i];j--)dp[j]max(dp[j],1.0-(1-dp[j-a[i]])*(1-b[i]));printf(%.1f%%\n,dp[n]*100);//coutdp[n]*100%endl;
}
