首页 > [NOI1999]钉子和小球
头像 活泼泼
发表于 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的形式输出 思路 概率不好处理,不妨认为小球每下落一层就分裂成两个,在有钉子的地方,一个去左边 展开全文