首页 > 代码库 > codeforces#253 D - Andrey and Problem里的数学知识
codeforces#253 D - Andrey and Problem里的数学知识
这道题是这种,给主人公一堆事件的成功概率,他仅仅想恰好成功一件。
于是,问题来了,他要选择哪些事件去做,才干使他的想法实现的概率最大。
我的第一个想法是枚举,枚举的话我想到用dfs,但是认为太麻烦。
于是想是不是有什么规律,于是推导了一下,推了一个出来,写成代码提交之后发现是错的。
最后就没办法了,剩下的时间不够写dfs,于是就放弃了。
今天看thnkndblv的代码,代码非常短,于是就想肯定是有什么数学规律,于是看了一下,
果然如此。
是这种,还是枚举,当然是有技巧的,看我娓娓道来。
枚举的话,如果总共同拥有n件事件,
从中选择1件事情去做,实现的概率最大是多少,
选择2件事情去做,实现的概率最大是多少,以此类推到选择n件事情去做。
于是就会得到n个结果,里面最大的那个就是实现主人公想法的最大概率。
这种话要从n件事件中随意选出1件事情然后比概率,随意选出2件事情然后比概率……随意选出n件事情然后比概率
还是要搜索。
可是这里就有数学知识了,能够不用搜索,做法是这种:
将n个事件成功的概率从大到小排序,
然后,
仅仅选择前1件事去做成功的概率就是“从中选择1件事情去做,最大的实现概率”
仅仅选择前2件事去做成功的概率就是“从中选择2件事情去做,最大的实现概率”
以此类推。
有了这个,这道题就非常easy了,至于为什么这样做能够,无法证明,假设有人证明的话,欢迎留言讨论,附上原题以及地址和我后来AC的代码例如以下:
http://codeforces.com/contest/443/problem/D
Andrey needs one more problem to conduct a programming contest. He has n friends who are always willing to help. He can ask some of them to come up with a contest problem. Andrey knows one value for each of his fiends — the probability that this friend will come up with a problem if Andrey asks him.
Help Andrey choose people to ask. As he needs only one problem, Andrey is going to be really upset if no one comes up with a problem or if he gets more than one problem from his friends. You need to choose such a set of people that maximizes the chances of Andrey not getting upset.
The first line contains a single integer n(1?≤?n?≤?100) — the number of Andrey‘s friends. The second line containsn real numbers pi(0.0?≤?pi?≤?1.0) — the probability that thei-th friend can come up with a problem. The probabilities are given with at most 6 digits after decimal point.
Print a single real number — the probability that Andrey won‘t get upset at the optimal choice of friends. The answer will be considered valid if it differs from the correct one by at most10?-?9.
#include<iostream> #include<algorithm> using namespace std; bool cmp(double a,double b) { return a>b; } int main() { int n,i,j,k; double a[110],x,sum,MAX; scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf",&a[i]); sort(a,a+n,cmp); MAX=0; for(i=1;i<=n;i++) { sum=0; for(j=0;j<i;j++) { x=a[j]; for(k=0;k<i;k++) { if(j!=k) x*=1-a[k]; } sum+=x; } MAX=max(sum,MAX); } printf("%.12lf\n",MAX); }
codeforces#253 D - Andrey and Problem里的数学知识