首页
比赛
题库
课程
竞赛讨论区
登录
/
注册
去牛客
首页
>
[NOI1999]钉子和小球
4条解析
开通博客写题解
活泼泼
发表于 2021-07-13 08:02:24
一开始我去考虑每个空格接受的球,后来发现想复杂了。如果最上面定义为第0行,最下面是第n-1行,那么我们可以手动补充第n行,也就是把最下面的每个格子都看成一个钉子。这样就不用考虑空格了,只需考虑钉子的事情。 令dp[i][j]为走到第i行第j列的球数,sum为最后一行的总和,那么所求的答案就是dp[n
展开全文
在刷题的单身狗很开心
发表于 2023-10-11 20:06:55
本题动态规划问题的状态转移很明显在小球下落的每一层里面发生变化,所以使用二维dp[i][j]来表示某一行某一个钉子或者去掉的钉子所拥有的小球。 题目要求最后以分数的方式给出答案,那么我们可以以小球的数量比下手,小球每进过一次钉子就会分裂成两个,这样就去考虑他到达底部某个槽子里面有多少个小球,然
展开全文
tydou
发表于 2025-03-21 09:01:38
萌新蒻够第一次写题解呜呜 先把整个无论是钉子还空格都视为能到达的位置用二维数组存储能到达的概率分子,n不太大空间问题不大。 如果n层则最后概率分母可以表示为2^n,gailv = (long) Math.pow(2, n);只需要把这个初始化后最上面向下分就行。 d = n * 2 + 1; z
展开全文
Z_L_G
发表于 2025-06-27 19:02:06
题意 一个竖直放置的三角形模板,钉着n(n+1)/2颗钉子,最底下有(n+1)个格子 从最顶上落下一个小球,小球碰到钉子落向两边的概率相等 求去除m个钉子后,落到最底下第m+1格的概率是多少,以a/b的形式输出 思路 概率不好处理,不妨认为小球每下落一层就分裂成两个,在有钉子的地方,一个去左边
展开全文
查看本题
查看本题讨论
相关比赛
209-NOI历年真题练习
进入比赛
345-NOI1999比赛真题
进入比赛
24213-2021秋季算法入门班第七章习题:动态规划1
进入比赛
26879-蓝桥训练4(动态规划)
进入比赛
28218-动态规划1
进入比赛
等你来战
查看全部
2025年第一届上海师范大学程序设计竞赛(同步赛)
报名截止时间:2025-07-13 18:00
牛客周赛 Round 100
报名截止时间:2025-07-13 21:00
2025牛客暑期多校训练营1
报名截止时间:2025-07-15 17:00
2025牛客暑期多校训练营2
报名截止时间:2025-07-17 17:00
牛客周赛 Round 101
报名截止时间:2025-07-20 21:00
"现代汽车前瞻杯"2025牛客暑期多校训练营3
报名截止时间:2025-07-22 17:00
2025牛客暑期多校训练营4
报名截止时间:2025-07-24 17:00
扫描二维码,关注牛客
意见反馈
下载牛客APP,随时随地刷题