首页 > [NOI1999]钉子和小球
开通博客写题解
头像 活泼泼
发表于 2021-07-13 08:02:24
一开始我去考虑每个空格接受的球，后来发现想复杂了。如果最上面定义为第0行，最下面是第n-1行，那么我们可以手动补充第n行，也就是把最下面的每个格子都看成一个钉子。这样就不用考虑空格了，只需考虑钉子的事情。 令dp[i][j]为走到第i行第j列的球数，sum为最后一行的总和，那么所求的答案就是dp[n 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-10-11 20:06:55
本题动态规划问题的状态转移很明显在小球下落的每一层里面发生变化，所以使用二维dp[i][j]来表示某一行某一个钉子或者去掉的钉子所拥有的小球。 题目要求最后以分数的方式给出答案，那么我们可以以小球的数量比下手，小球每进过一次钉子就会分裂成两个，这样就去考虑他到达底部某个槽子里面有多少个小球，然 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 tydou
发表于 2025-03-21 09:01:38
萌新蒻够第一次写题解呜呜 先把整个无论是钉子还空格都视为能到达的位置用二维数组存储能到达的概率分子，n不太大空间问题不大。 如果n层则最后概率分母可以表示为2^n,gailv = (long) Math.pow(2, n);只需要把这个初始化后最上面向下分就行。 d = n * 2 + 1; z 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”