题目名称 | 3140. (USACO Dec18)平衡木 |
---|---|
输入输出 | balance_beam.in/out |
难度等级 | ★★★☆ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 11 |
题目来源 | Satoshi 于2019-05-13加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:5, 提交:20, 通过率:25% | ||||
LGLJ | 100 | 0.168 s | 11.32 MiB | C++ |
Satoshi | 100 | 0.262 s | 15.19 MiB | C++ |
rainy | 100 | 0.295 s | 16.05 MiB | C++ |
Sakura | 100 | 0.903 s | 22.05 MiB | C++ |
梦那边的美好ET | 100 | 0.949 s | 15.95 MiB | C++ |
HYOI_ingn | 27 | 1.690 s | 206.30 MiB | C++ |
HYOI_ingn | 27 | 7.460 s | 98.74 MiB | C++ |
HYOI_ingn | 27 | 7.490 s | 98.74 MiB | C++ |
梦那边的美好ET | 27 | 8.178 s | 14.42 MiB | C++ |
Satoshi | 27 | 8.192 s | 4.43 MiB | C++ |
本题关联比赛 | |||
20191022轻松模拟测试 |
关于 (USACO Dec18)平衡木 的近10条评论(全部评论) |
---|
(译者:Satoshi, 转载请注明出处)
为了给谷仓的新畜栏省钱,奶牛贝茜开始在当地的杂戏团表演。通过在很高的平衡木上来回走动来展现她非凡的平衡感。
贝茜每次赚多少钱跟她在最终在平衡木的哪一个位置跳下来有关。平衡木从左到右的位置标为$0,1,..., N+1$。如果贝茜到达了位置$0$或者位置$N+1$她就会从平衡木的一端掉下来并且(很悲伤的)赚不到一分钱。
如果贝茜在一个给定的位置k, 她可以做下面两件事中的一件:
1. 投掷一枚硬币。如果是反面,贝茜移动到位置$k-1$;如果是正面,贝茜移动到位置$k+1$.(正反面的概率各是$\frac {1}{2}$)
2. 从平衡木上跳下来并且获得收入$f(k)$$(0<=f(k)<=10^9)$
因为移动取决于随机投掷硬币,贝茜意识到她不能保证任何特定的收入。然而,根据贝茜开始的位置,她想知道获得收入的最高期望(通过最合适的策略)。比如说,如果她的策略将会有$\frac {1}{2}$的机率赚到$10$块钱,$\frac {1}{4}$的机率赚到$8$块钱,$\frac {1}{2}$的机率赚到$0$块钱,那么她的收入期望将会是加权平均数$10(1/2)+8(1/4)+0(1/4)=7$。
第一行包含一个正整数$N$。剩下的N行包含$f(1)...f(N)$
输出$N$行,第$i$行四舍五入到收入的$10^5$倍
2 1 3
150000 300000
$N/A$
与标准答案差1以内即可通过
http://www.usaco.org/index.php?page=viewproblem2&cpid=864
USACO Dec 2018 Platinum Division