首页 > 代码库 > 概率dp sgu495
概率dp sgu495
Kids and Prizes
Time Limit:250MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64uAppoint description:
Description
ICPC (International Cardboard Producing Company) is in the business of producing cardboard boxes. Recently the company organized a contest for kids for the best design of a cardboard box and selected M winners. There are N prizes for the winners, each one carefully packed in a cardboard box (made by the ICPC, of course). The awarding process will be as follows:
- All the boxes with prizes will be stored in a separate room.
- The winners will enter the room, one at a time.
- Each winner selects one of the boxes.
- The selected box is opened by a representative of the organizing committee.
- If the box contains a prize, the winner takes it.
- If the box is empty (because the same box has already been selected by one or more previous winners), the winner will instead get a certificate printed on a sheet of excellent cardboard (made by ICPC, of course).
- Whether there is a prize or not, the box is re-sealed and returned to the room.
Input
The first and only line of the input file contains the values of N and M ( ).
Output
The first and only line of the output file should contain a single real number: the expected number of prizes given out. The answer is accepted as correct if either the absolute or the relative error is less than or equal to 10 -9.
Sample Input
sample input | sample output |
5 7 | 3.951424 |
sample input | sample output |
4 3 | 2.3125 |
题意:有n件奖品装在n个箱子里,M个人选择其中的一个箱子,每个人取出一个箱子,如果有奖品取出,后将箱子放回,后面的人继续取箱子.问最终取出箱子个数的期望。
另dp[i]表示第i个人拿到奖品的概率则,dp[1]=1;若i-1取到了奖品则i获得奖品的概率为dp[i-1]-1/n,否则i得到奖品的概率为dp[i-1].转移方程为dp[i]=dp[i-1]*(dp[i-1]-1/n)+(1-dp[i-1])*dp[i-1].、
/************************************************************************* > File Name: t.cpp > Author: acvcla > Mail: acvcla@gmail.com > Created Time: 2014年10月21日 星期二 21时33分55秒 ************************************************************************/ #include<iostream> #include<algorithm> #include<cstdio> #include<vector> #include<cstring> #include<map> #include<queue> #include<stack> #include<string> #include<cstdlib> #include<ctime> #include<set> #include<math.h> using namespace std; typedef long long LL; const int maxn = 1e5 + 10; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back int n,m,f; double dp[maxn]; int main(int argc, char const *argv[]) { while(~scanf("%d%d",&n,&m)){ memset(dp,0,sizeof dp); dp[1]=1; double ans=1; for(int i=2;i<=m;i++){ dp[i]=dp[i-1]*(dp[i-1]-1.0/n)+(1-dp[i-1])*dp[i-1]; ans+=dp[i]; } printf("%.10f\n",ans); } return 0; }
概率dp sgu495
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。