SGU 495 Kids and Prizes:期望dp / 概率dp / 推公式
题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=495
题意:
有n个礼物盒,m个人。
最开始每个礼物盒中都有一个礼物。
m个人依次随机选一个盒子,如果有礼物就拿走,然后放回空盒子。
问你所有人得到总礼物数的期望。
题解:
三种做法:期望dp,概率dp,推公式
一、期望dp
表示状态:
dp[i] = 该第i个人拿箱子时的总礼物的期望
找出答案:
ans = dp[m]
如何转移:
对于第i个人,拿到礼物或没拿到。
(1)φ(没拿到) = dp[i] P(没拿到) = dp[i]/n
(2)φ(拿到) = dp[i]+1 P(拿到) = (n-dp[i])/n
综上:dp[i+1] = dp[i] * dp[i]/n + (dp[i]+1) * (n-dp[i])/n
边界条件:
dp[0] = 0
还没开始拿的时候礼物数为0
二、概率dp
表示状态:
dp[i] = 第i个人拿到礼物的概率
找出答案:
ans = ∑ dp[i]
每个人得到礼物的概率 * 得到礼物的数量(为1) 之和。
如何转移:
对于第i个人,拿到礼物或没拿到。
(1)没拿到:dp[i+1]依然等于dp[i],没拿到礼物的概率为1-dp[i].
(2)拿到:dp[i+1] = dp[i] - 1/n,拿到的概率为dp[i].
综上:dp[i+1] = dp[i] * (1 - dp[i]) + (dp[i] - 1/n) * dp[i]
边界条件:
dp[0] = 1
所有盒子里都有礼物,第0个人一定拿到礼物。
三、推公式
m个人是独立的。
对于每个礼物不被人选中的概率为((n-1)/n)^m
那么不被选中的礼物数的期望就是 n*((n-1)/n)^m
所以答案就是 n-n*((n-1)/n)^m
AC Code(expectation):
// state expression:
// dp[i] = expectation
// i: considering ith person
//
// find the answer:
// ans = dp[m]
//
// transferring:
// dp[i+1] = dp[i] * dp[i]/n + (dp[i]+1) * (n-dp[i])/n
//
// boundary:
// dp[0] = 0
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_M 100005 using namespace std; int n,m;
double dp[MAX_M]; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<m;i++)
{
dp[i+]=dp[i]*dp[i]/n+(dp[i]+1.0)*(n-dp[i])/n;
}
printf("%.10f\n",dp[m]);
}
AC Code(probability):
// state expression:
// dp[i] = probability
// i: ith person got a gift
//
// find the answer:
// sigma dp[i]
//
// transferring:
// dp[i+1] = dp[i] * (1 - dp[i]) + (dp[i] - 1/n) * dp[i]
//
// boundary:
// dp[0] = 1
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_M 100005 using namespace std; int n,m;
double ans=;
double dp[MAX_M]; int main()
{
scanf("%d%d",&n,&m);
dp[]=;
for(int i=;i<m;i++)
{
dp[i+]=dp[i]*(1.0-dp[i])+(dp[i]-1.0/n)*dp[i];
ans+=dp[i];
}
printf("%.10f\n",ans);
}
AC Code(公式):
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h> using namespace std; int n,m; int main()
{
scanf("%d%d",&n,&m);
printf("%.10f\n",n-n*pow((n-1.0)/n,m));
}
最新文章
- iOS中为网站添加图标到主屏幕
- 多条件动态LINQ 组合查询
- Sharepoint增加修改密码功能
- scala学习笔记(6):闭包
- LeetCode Binary Tree Level Order Traversal (按层收集元素)
- [C++]VS2010功能设置
- [WebGL入门]十四,绘制多边形
- 终端command总结
- iOS开发实现登陆
- html5页面增强元素
- 学习MVC遇到的问题
- FastReport的再次使用
- CentOS采用grub进 single状态
- UAC
- WebService的调用
- .net大型平台通过Nginx做负载均衡(Web层、中间服务层、DB层)
- 添加打印功能 iOS
- linux 使用内存作为 /tmp 临时文件夹
- 用Python实现多站点运维监控
- eclipse上的.properties文件中文编辑显示处理