题目链接: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;
}
分享到:
相关推荐
前端开源库-gulp-expect-filegulp expect file,gulp.js管道中的expect文件
前端项目-expect.js,节点和浏览器的BDD样式断言。
前端开源库-expect-jsx期望JSX,对于Mjackson,ToEqualJSX/Expect
帕拉米科期望 作品由 介绍 Paramiko Expect为Paramiko SSH库提供了一个类似于期望的扩展,该脚本库允许脚本通过真正的SSH连接... # Connect to the host client . connect ( hostname = hostname , username = usernam
前端开源库-expect-jsx.zip
开源项目-a8m-expect.zip,expect - Minimalist BDD-style assertions for Go.
linux-expect模拟键盘输入实现定时登录教程(内含expect安装包、教程)
简单介绍tcl语言以和expect语法以及使用方法
前端项目-expect,Write better assertions
expect.deb离线包,包含 expect_5.45-2_amd64.deb tcl8.5_8.5.11-1ubuntu1_amd64.deb两个 使用命令 dpkg --install expect_5.45-2_amd64.deb dpkg --install tcl8.5_8.5.11-1ubuntu1_amd64.deb 可以直接进行安装,不...
linux交互式编程expect的基础包
运行脚本后,批量扫描主机自动执行ssh-copy-id,自动输入密码。完成批量主机ssh无口令配置
现在将jest-expect-json导入您的测试中! 建立在之上,`jest-expect-json为jest添加了有用的json测试! 设置 将jest-expect-json添加到您的测试文件中,如下所示: import 'jest-expect-json' ; 方法 jsonMatching...
c , err := expect . NewConsole ( expect . WithStdout ( os . Stdout )) if err != nil { log . Fatal ( err ) } defer c . Close () cmd := exec . Command ( "vi" ) cmd . Stdin = c . Tty () cmd . ...
在centos-7上,本人下载好的安装包。 yum install --downloadonly --downloaddir=./ expect expect-dev tcl 可以直接安装,摆脱网络依赖。
在 devDependencies 中保存jasmine-expect-count npm install jasmine-expect-count --save-dev 然后要求它 require ( "jasmine-expect-count" ) ; 在你的测试之前。 使用 Jasmine Expect Count 允许您指定在it...
这个是讲解Tcl/tk 中Expect用法的书,讲的同时结合实例,很易懂。绝对是入门的好材料。
eslint-plugin-chai-expect-keywords ESLint插件,用于检查chai.js Expect expect()断言中不受支持的关键字。 Chai允许您链接单词以使可读的断言,但是不幸的是,您可以包含chai一无所知的关键字,并且它不会通过...
npm install ts-expect --save 用法 TS Expect导出了一个完全不执行任何操作的函数,名为expectType 。 取而代之的是,它取决于TypeScript编译器,并且可以对传递给expectType的“值”类型进行测试的泛型可以在类型...