uva 11427 - Expect the Expected(概率)
2024-10-12 00:19:36
题目链接:uva 11427 - Expect the Expected
题目大意:你每天晚上都会玩纸牌,每天固定最多玩n盘,每盘胜利的概率为p,你是一个固执的人,每天一定要保证胜局的比例大于p才会结束游戏,若n局后仍没有,就会不开心,然后以后再也不完牌,问说你最多会玩多少个晚上。
解题思路:当j/i ≤ p时有dp(i-1,j) (1-p) + dp(i-1, j-1)
p,其它dp(i,j) = 0.Q=∑d(n,i)
列出数学期望公式:
EX=Q+2Q(1−Q)+3Q(1−Q)2+…
s=EXQ=1+2(1−Q)+3(1−Q)2+…
(1−Q)∗s=(1−Q)+2(1−Q)2+3(1−Q)3+…
EX=Qs=1+(1−Q)+(1−Q)2+(1−Q)3…
为等比数列,依据等比数列求和公式,n趋近无穷大是为1/Q
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 105;
double dp[maxn][maxn];
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
int a, b, n;
scanf("%d/%d%d", &a, &b, &n);
double p = (double)a / b;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
dp[0][1] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j * b <= a * i; j++) {
dp[i][j] = dp[i-1][j] * (1-p);
if (j)
dp[i][j] += dp[i-1][j-1] * p;
}
}
double q = 0;
for (int i = 0; i * b <= a * n; i++)
q += dp[n][i];
printf("Case #%d: %d\n", kcas, (int)(1/q));
}
return 0;
}
最新文章
- Linux LVM学习总结&mdash;&mdash;删除物理卷
- Compress a Folder/Directory via Perl5
- xml使用系统整理
- Articulate Studio课间制作工具
- Android核心基础(四)
- Ubuntu下配置smb服务器
- 08 - 删除vtkDataObject中的SetWholeExtent() 方法 VTK 6.0 迁移
- 简单的批量读取外部insert文并插入DB
- HDU 1573 X问题 中国剩余定理
- Hadoop无法上传文件查找原因
- 小白的Python之路 day1 模块初识
- form表单action=";";的作用
- python穷举法解数独
- 微信小程序设置背景铺满全屏
- 【Spring】24、<;load-on-startup>;0<;/load-on-startup>;配置
- 7.15python进程锁
- 学习Linux二(创建、删除文件和文件夹命令)
- vue-router进阶笔记
- 维诺图(Voronoi Diagram)分析与实现(转)
- java从键盘输入一组数据,输出其最大值,平均值,最小值没法输出