解题了解题了，蜂蜜罐子排列

STEM版，合并数学，物理，化学，科学，工程，机械。不包括生物、医学相关，和计算机相关内容。

版主： verdelite， TheMatrix

回复
头像
verdelite（众傻之傻）楼主
论坛元老
论坛元老
帖子互动： 926
帖子： 22840
注册时间： 2022年 7月 21日 23:33

解题了解题了，蜂蜜罐子排列

帖子 由 verdelite（众傻之傻）楼主 »

出个啥题你们都能弄到群论之类的拔高（其实是抽象）的代数上去。这个题看你们怎么抽象。

有个阿拉伯的商人，在流着奶和蜜的地方弄蜂蜜来卖。他把品质用数字按照顺序标识。例如1就比2的品质高。也比10 高。现在他有10罐蜂蜜，排成上下两排，上面罐子的叠在下面的罐子上面，各5罐。例如，
1,2,3,4,5
6,7,8,9,10
商人说，我排的规矩是，对于一罐蜂蜜，比它品质差的罐子，就不能排在它正左边或者正上边。

有天一个顾客听到他又在说他的规矩，就说，其实也不用像前面图里面这样排。其实还可以这样：
1，2，5，6，8
3，4，7，9，10
注意，上图中3虽然是在2的左边，但是我们看2的时候只看它右边和下面的两个是不是满足要求。所以上面这个排布是可以的。

问有几种排法。看你们怎么抽象，哈哈。
没有光子；也没有量子能级，量子跃迁，量子叠加，量子塌缩和量子纠缠。
页首
头像
YWY（夜未央）
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动： 1267
帖子： 13856
注册时间： 2022年 7月 22日 17:25

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 YWY（夜未央） »

let me think.
上次由 YWY 在 2023年 1月 21日 23:04 修改。
持仓抄底锁利，你钱你定
看牛观猪喊熊，自娱自乐
股市变幻莫测，不作不死
赌途曲折无常，吃枣药丸
页首
头像
TheMatrix
论坛支柱
论坛支柱
2024年度优秀版主
TheMatrix 的博客
帖子互动： 264
帖子： 13266
注册时间： 2022年 7月 26日 00:35

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 TheMatrix »

verdelite 写了： 2023年 1月 21日 22:34 出个啥题你们都能弄到群论之类的拔高（其实是抽象）的代数上去。这个题看你们怎么抽象。

有个阿拉伯的商人，在流着奶和蜜的地方弄蜂蜜来卖。他把品质用数字按照顺序标识。例如1就比2的品质高。也比10 高。现在他有10罐蜂蜜，排成上下两排，上面罐子的叠在下面的罐子上面，各5罐。例如，
1,2,3,4,5
6,7,8,9,10
商人说，我排的规矩是，对于一罐蜂蜜，比它品质差的罐子，就不能排在它正左边或者正上边。

有天一个顾客听到他又在说他的规矩，就说，其实也不用像前面图里面这样排。其实还可以这样：
1，2，5，6，8
3，4，7，9，10
注意，上图中3虽然是在2的左边，但是我们看2的时候只看它右边和下面的两个是不是满足要求。所以上面这个排布是可以的。

问有几种排法。看你们怎么抽象，哈哈。
感觉不容易。
页首
FGH
论坛精英
论坛精英
帖子互动： 101
帖子： 6927
注册时间： 2022年 7月 25日 16:30

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 FGH »

计算机暴力求解
页首
lbs
小有名气
小有名气
帖子互动： 1
帖子： 33
注册时间： 2022年 12月 24日 09:49

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 lbs »

口算不太会。不过这个问题用算法是可以做的。倒也不用暴力穷举（虽然总共就 10 个数，暴力穷举确实也能秒算）。其实可以用 DP 的思想。注意到这个条件限制实际是说：相邻的两个数，右边的总比左边大，下边的也总比上边的大。这个就构成了一个这十个位置的序关系（下面是个粗糙的示意图）：
1 -> 2 -> ...
| |
\/ \/
6 -> 7 -> ...

这个限制就决定了，1 只能在最左上角（因为没有再比它小的了）。为了知道总共有多少种方法，我们就考虑，依次把 1, 2, 3, ..., 10 放到十个位置里，能有多少种放法。放完 1 （必须在左上角）之后，再放 2 的位置，可以是上面示意图里 2 的位置，或者 6 的位置。以此类推。同时注意到，每次放置的时候，只能在图像中最左上的位置（可能有一个或两个 ）来放，分别对应如下的情形（下图中 x 表示已放置，o 表示未放置）：
1. 只有一个新的位置：
x x o o o
x x o o o
(此时已经放完 1~4， 5 只能放在第一排第三列）
2. 有两个新的位置：
x x x o o
x o o o o
(此时已经放完 1~4， 5可能放在一排 4 列或者二排二列）

接下来就是怎么记录这种状态了。不难发现，我们可以用一个二元数对 (a, b) 来表示还未填充的位置的状态，其中 a 表示第一排的剩余空数，b 表示第二排的。以如上两个情形为例，情形一对应的状态就是 (3, 3)，情形 2 对应的状态就是 (2, 4)。注意， 根据规则，a <= b 总是成立的。
我们再以 f(a, b) 来表示 (a, b) 状态对应的可能的填充方式的总数，那么就会得到如下的递推公式：
（情形还是和上面保持一致）
情形 1: a = b
那么 f(a, b) = f(a - 1, b)
（也就是说你只能填一个位置）
情形 2: a < b
那么 f(a, b) = f(a - 1, b) + f(a, b - 1)
（也就是说你能填两个位置，第一行最左边的剩余位置，或者第二行最左边的剩余位置，填完后 分别对应 a - 1 和 b - 1，总方法数就是把这两个方法数加起来）
边界条件： f(0, 0) = 1, f(-1, ...) = f(..., -1) = 0
（即都填满后剩下 “唯一” 一种方案，即不填。对这种比较抽象的边界条件不太适应的同学，也可以手动补一些自己可以直观接受的边界条件，比如 f(1, 1) = f(0, 1) = f(0, 2) = ... f(0, 5) = 0）
这样 DP 的 complexity 就是 O(罐子^2)。这个题目里只有 10 个 罐子，还是比较好算的。当然，如果你有 1w 个罐子，分上下排成 5000, 5000 排，老夫的算法还是可以在 O(5000^2) 给出结果的，毫秒级！

老夫本想 coding 一下算出楼主的答案。但想想既然只是 O(25), 不妨来手推一下吧：
我们想求的是 f(5, 5)，那么依次计算即可：
f(0, 0) = 1
f(0, 1) = 1
f(1, 1) = 1
f(0, 2) = 1
f(1, 2) = f(0, 2) + f(1, 1) = 2
f(2, 2) = f(1, 2) = 2
f(0, 3) = 1
f(1, 3) = f(0, 3) + f(1, 2) = 3
f(2, 3) = f(1, 3) + f(2, 2) = 3 + 2 = 5
f(3, 3) = f(2, 3) = 5
f(0, 4) = 1
f(1, 4) = f(0, 4) + f(1, 3) = 4
f(2, 4) = f(1, 4) + f(2, 3) = 4 + 5 = 9
f(3, 4) = f(2, 4) + f(3, 3) = 9 + 5 = 14
f(4, 4) = f(3, 4) = 14
f(0, 5) = 1
f(1, 5) = f(0, 5) + f(1, 4) = 5
f(2, 5) = f(1, 5) + f(2, 4) = 5 + 9 = 14
f(3, 5) = f(2, 5) + f(3, 4) = 14 + 14 = 28
f(4, 5) = f(3, 5) + f(4, 4) = 28 + 14 = 42
f(5, 5) = f(4, 5) = 42

所以最终有 42 种方法！
我佬写着写着，总感觉这里面有个什么递推公式，所以或许可以直接列出式子而不是用DP 的方式来做状态递归（就好比斐波那契有个通项公式，而不需要用O(n) 的方式去算第 n 项一样）。但我佬的脑子不太够用了，留给后人继续深挖吧。
x1 图片
页首
头像
YWY（夜未央）
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动： 1267
帖子： 13856
注册时间： 2022年 7月 22日 17:25

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 YWY（夜未央） »

abcde
fghij
It suffices to arrange the top row, as the bottom row must take the remaining numbers in increasing order from left to right. An arrangement for the top row works if and only if

a < 2, b < 4, c < 6, d < 8, e < 10 as well as 0 < a < b < c < d < e

So, we can exhaust all possibilities pretty easily. But I can not find a nice formula for the total number.

类比下面的游戏：10个格子列成一排，依次标着1，2，……，10，你站第1格子里，向前跳4次，每次必须往前面的格子里跳（不能原地不动或后退），第一次跳落地不能超过第3格，第二次跳不能超过第5格，第三次跳不能超过第7格，第四次跳不能超过第9格，问一共有多少种跳法。

我找不出公式，就指望大家了。
持仓抄底锁利，你钱你定
看牛观猪喊熊，自娱自乐
股市变幻莫测，不作不死
赌途曲折无常，吃枣药丸
页首
Caravel
论坛元老
论坛元老
Caravel 的博客
帖子互动： 564
帖子： 24664
注册时间： 2022年 7月 24日 17:21

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 Caravel »

YWY 写了： 2023年 1月 22日 00:09
abcde
fghij
It suffices to arrange the top row, as the bottom row must take the remaining numbers in increasing order from left to right. An arrangement for the top row works if and only if

a < 2, b < 4, c < 6, d < 8, e < 10 as well as 0 < a < b < c < d < e

So, we can exhaust all possibilities pretty easily. But I can not find a nice formula for the total number.

类比下面的游戏：10个格子列成一排，依次标着1，2，……，10，你站第1格子里，向前跳4次，每次必须往前面的格子里跳（不能原地不动或后退），第一次跳落地不能超过第3格，第二次跳不能超过第5格，第三次跳不能超过第7格，第四次跳不能超过第9格，问一共有多少种跳法。

我找不出公式，就指望大家了。
1到10按顺序排，用a,b表示两排，则a1 必须是1，因为小于所有的数，b5必须是10，第一排先选出4个数来，剩下的填到第二排，最多也c(8,4) = 70, 在分析一下每种可行不

进一步分析充分必要条件是分析第一排，si是第i数根i-1个数之间的空隙，则必须有sum(si) < i，否则说明比当前数小的数可以填到这个数下面。
举一个不成立的例子就清楚了

1 2 4 8 9
3 5 6 7 10

第一排第四个数字8，总共跳过了4, 不满足条件

所以分析第一排数字即可, 假设
s1 = 0
s1 + s2 < 2
s1 + s2 + s3 < 3
s1 + s2 + s3 + s4 < 4
s1 + s2 + s3 + s4+ s5 < 5

总数确实是42
上次由 Caravel 在 2023年 1月 22日 02:04 修改。
页首
头像
verdelite（众傻之傻）楼主
论坛元老
论坛元老
帖子互动： 926
帖子： 22840
注册时间： 2022年 7月 21日 23:33

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 verdelite（众傻之傻）楼主 »

lbs 写了： 2023年 1月 22日 00:04 口算不太会。不过这个问题用算法是可以做的。倒也不用暴力穷举（虽然总共就 10 个数，暴力穷举确实也能秒算）。其实可以用 DP 的思想。注意到这个条件限制实际是说：相邻的两个数，右边的总比左边大，下边的也总比上边的大。这个就构成了一个这十个位置的序关系（下面是个粗糙的示意图）：
1 -> 2 -> ...
| |
\/ \/
6 -> 7 -> ...

这个限制就决定了，1 只能在最左上角（因为没有再比它小的了）。为了知道总共有多少种方法，我们就考虑，依次把 1, 2, 3, ..., 10 放到十个位置里，能有多少种放法。放完 1 （必须在左上角）之后，再放 2 的位置，可以是上面示意图里 2 的位置，或者 6 的位置。以此类推。同时注意到，每次放置的时候，只能在图像中最左上的位置（可能有一个或两个 ）来放，分别对应如下的情形（下图中 x 表示已放置，o 表示未放置）：
1. 只有一个新的位置：
x x o o o
x x o o o
(此时已经放完 1~4， 5 只能放在第一排第三列）
2. 有两个新的位置：
x x x o o
x o o o o
(此时已经放完 1~4， 5可能放在一排 4 列或者二排二列）

接下来就是怎么记录这种状态了。不难发现，我们可以用一个二元数对 (a, b) 来表示还未填充的位置的状态，其中 a 表示第一排的剩余空数，b 表示第二排的。以如上两个情形为例，情形一对应的状态就是 (3, 3)，情形 2 对应的状态就是 (2, 4)。注意， 根据规则，a <= b 总是成立的。
我们再以 f(a, b) 来表示 (a, b) 状态对应的可能的填充方式的总数，那么就会得到如下的递推公式：
（情形还是和上面保持一致）
情形 1: a = b
那么 f(a, b) = f(a - 1, b)
（也就是说你只能填一个位置）
情形 2: a < b
那么 f(a, b) = f(a - 1, b) + f(a, b - 1)
（也就是说你能填两个位置，第一行最左边的剩余位置，或者第二行最左边的剩余位置，填完后 分别对应 a - 1 和 b - 1，总方法数就是把这两个方法数加起来）
边界条件： f(0, 0) = 1, f(-1, ...) = f(..., -1) = 0
（即都填满后剩下 “唯一” 一种方案，即不填。对这种比较抽象的边界条件不太适应的同学，也可以手动补一些自己可以直观接受的边界条件，比如 f(1, 1) = f(0, 1) = f(0, 2) = ... f(0, 5) = 0）
这样 DP 的 complexity 就是 O(罐子^2)。这个题目里只有 10 个 罐子，还是比较好算的。当然，如果你有 1w 个罐子，分上下排成 5000, 5000 排，老夫的算法还是可以在 O(5000^2) 给出结果的，毫秒级！

老夫本想 coding 一下算出楼主的答案。但想想既然只是 O(25), 不妨来手推一下吧：
我们想求的是 f(5, 5)，那么依次计算即可：
f(0, 0) = 1
f(0, 1) = 1
f(1, 1) = 1
f(0, 2) = 1
f(1, 2) = f(0, 2) + f(1, 1) = 2
f(2, 2) = f(1, 2) = 2
f(0, 3) = 1
f(1, 3) = f(0, 3) + f(1, 2) = 3
f(2, 3) = f(1, 3) + f(2, 2) = 3 + 2 = 5
f(3, 3) = f(2, 3) = 5
f(0, 4) = 1
f(1, 4) = f(0, 4) + f(1, 3) = 4
f(2, 4) = f(1, 4) + f(2, 3) = 4 + 5 = 9
f(3, 4) = f(2, 4) + f(3, 3) = 9 + 5 = 14
f(4, 4) = f(3, 4) = 14
f(0, 5) = 1
f(1, 5) = f(0, 5) + f(1, 4) = 5
f(2, 5) = f(1, 5) + f(2, 4) = 5 + 9 = 14
f(3, 5) = f(2, 5) + f(3, 4) = 14 + 14 = 28
f(4, 5) = f(3, 5) + f(4, 4) = 28 + 14 = 42
f(5, 5) = f(4, 5) = 42

所以最终有 42 种方法！
我佬写着写着，总感觉这里面有个什么递推公式，所以或许可以直接列出式子而不是用DP 的方式来做状态递归（就好比斐波那契有个通项公式，而不需要用O(n) 的方式去算第 n 项一样）。但我佬的脑子不太够用了，留给后人继续深挖吧。
42是对的，我用python硬算了一下，费时几秒。 
import itertools
def OK(mylist):
    return(tuple(sorted(mylist[0:5]))==mylist[0:5] and
           tuple(sorted(mylist[5:10]))==(mylist[5:10]) and
           all([item1 < item2 for item1,item2 in zip(mylist[0:5],mylist[5:10])]))

results=[item for item in itertools.permutations(range(1,11)) if OK(item)]
for item in results:
    print(item)
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
(1, 2, 3, 4, 6, 5, 7, 8, 9, 10)
(1, 2, 3, 4, 7, 5, 6, 8, 9, 10)
(1, 2, 3, 4, 8, 5, 6, 7, 9, 10)
(1, 2, 3, 4, 9, 5, 6, 7, 8, 10)
(1, 2, 3, 5, 6, 4, 7, 8, 9, 10)
(1, 2, 3, 5, 7, 4, 6, 8, 9, 10)
(1, 2, 3, 5, 8, 4, 6, 7, 9, 10)
(1, 2, 3, 5, 9, 4, 6, 7, 8, 10)
(1, 2, 3, 6, 7, 4, 5, 8, 9, 10)
(1, 2, 3, 6, 8, 4, 5, 7, 9, 10)
(1, 2, 3, 6, 9, 4, 5, 7, 8, 10)
(1, 2, 3, 7, 8, 4, 5, 6, 9, 10)
(1, 2, 3, 7, 9, 4, 5, 6, 8, 10)
(1, 2, 4, 5, 6, 3, 7, 8, 9, 10)
(1, 2, 4, 5, 7, 3, 6, 8, 9, 10)
(1, 2, 4, 5, 8, 3, 6, 7, 9, 10)
(1, 2, 4, 5, 9, 3, 6, 7, 8, 10)
(1, 2, 4, 6, 7, 3, 5, 8, 9, 10)
(1, 2, 4, 6, 8, 3, 5, 7, 9, 10)
(1, 2, 4, 6, 9, 3, 5, 7, 8, 10)
(1, 2, 4, 7, 8, 3, 5, 6, 9, 10)
(1, 2, 4, 7, 9, 3, 5, 6, 8, 10)
(1, 2, 5, 6, 7, 3, 4, 8, 9, 10)
(1, 2, 5, 6, 8, 3, 4, 7, 9, 10)
(1, 2, 5, 6, 9, 3, 4, 7, 8, 10)
(1, 2, 5, 7, 8, 3, 4, 6, 9, 10)
(1, 2, 5, 7, 9, 3, 4, 6, 8, 10)
(1, 3, 4, 5, 6, 2, 7, 8, 9, 10)
(1, 3, 4, 5, 7, 2, 6, 8, 9, 10)
(1, 3, 4, 5, 8, 2, 6, 7, 9, 10)
(1, 3, 4, 5, 9, 2, 6, 7, 8, 10)
(1, 3, 4, 6, 7, 2, 5, 8, 9, 10)
(1, 3, 4, 6, 8, 2, 5, 7, 9, 10)
(1, 3, 4, 6, 9, 2, 5, 7, 8, 10)
(1, 3, 4, 7, 8, 2, 5, 6, 9, 10)
(1, 3, 4, 7, 9, 2, 5, 6, 8, 10)
(1, 3, 5, 6, 7, 2, 4, 8, 9, 10)
(1, 3, 5, 6, 8, 2, 4, 7, 9, 10)
(1, 3, 5, 6, 9, 2, 4, 7, 8, 10)
(1, 3, 5, 7, 8, 2, 4, 6, 9, 10)
(1, 3, 5, 7, 9, 2, 4, 6, 8, 10)
没有光子；也没有量子能级，量子跃迁，量子叠加，量子塌缩和量子纠缠。
页首
头像
YWY（夜未央）
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动： 1267
帖子： 13856
注册时间： 2022年 7月 22日 17:25

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 YWY（夜未央） »

类比下面的游戏：2n个格子列成一排，依次标着1，2，……，2n，你站外面，向前跳n次，第一次跳到第1格，然后每次必须往前面的格子里跳（不能原地不动或后退），第二次跳落地不能超过第3格，第三次跳不能超过第5格，……，第i次跳不能超过第2i - 1格，……，第n次跳不能超过第2n - 1格，问一共有多少种跳法。

Let f_i(k) be the total number of ways to land in the k-th square after i-th play. Let p(n) be the total number of plays the game. We have
f_1(1) = 1; p(1) = 1
f_2(2) = 1, f_2(3) = 1; p(2) = f_2(2) + f_2(3) = 2
f_3(3) = f_2(2) = 1, f_3(4) = p(2) = 2, f_3(5) = p(2) = 2; p(3) = 5 (the sum of the numbers on the left)
f_4(4) = f_3(3) = 1, f_4(5) = f_3(3) + f_3(4) = 3, f_4(6) = f_4(7) = p(3) = 5; p(4) = 14
f_5(5) = f_4(4) = 1, f_5(6) = f_4(4) + f_4(5) = 4, f_5(7) = f_4(4) + f_4(5) + f_4(6) = 9, f_5(8) = f_5(9) = p(4) = 14; p(5) = 42
f_6(6) = 1, f_6(7) = f_6(6) + f_5(6) = 5, f_6(8) = f_6(7) + f_5(7) = 14, f_6(9) = f_6(8) + f_5(8) = 28, f_6(10) = f_6(11) = p(5) = 42; p(6) = 132
...
f_n(n) = 1, f_n(n+1) = f_n(n) + f_{n-1}(n), ..., f_n(2n-3) = f_n(2n-4) + f_{n-1}(2n-4), f_n(2n-2) = f_n(2n-1) = p(n-1); p(n) = f_n(n) + ... + f_n(2n-1).

Note that p(n) is the same as the total number of arrangements of 2n many honey jars satisfying the conditions.

我找不出公式，就指望大家了。
上次由 YWY 在 2023年 1月 22日 11:02 修改。
持仓抄底锁利，你钱你定
看牛观猪喊熊，自娱自乐
股市变幻莫测，不作不死
赌途曲折无常，吃枣药丸
页首
头像
（ヅ）
论坛支柱
论坛支柱
帖子互动： 544
帖子： 11677
注册时间： 2022年 8月 21日 14:20

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 （ヅ） »

lbs 写了： 2023年 1月 22日 00:04 口算不太会。不过这个问题用算法是可以做的。倒也不用暴力穷举（虽然总共就 10 个数，暴力穷举确实也能秒算）。其实可以用 DP 的思想。注意到这个条件限制实际是说：相邻的两个数，右边的总比左边大，下边的也总比上边的大。这个就构成了一个这十个位置的序关系（下面是个粗糙的示意图）：
1 -> 2 -> ...
| |
\/ \/
6 -> 7 -> ...

这个限制就决定了，1 只能在最左上角（因为没有再比它小的了）。为了知道总共有多少种方法，我们就考虑，依次把 1, 2, 3, ..., 10 放到十个位置里，能有多少种放法。放完 1 （必须在左上角）之后，再放 2 的位置，可以是上面示意图里 2 的位置，或者 6 的位置。以此类推。同时注意到，每次放置的时候，只能在图像中最左上的位置（可能有一个或两个 ）来放，分别对应如下的情形（下图中 x 表示已放置，o 表示未放置）：
1. 只有一个新的位置：
x x o o o
x x o o o
(此时已经放完 1~4， 5 只能放在第一排第三列）
2. 有两个新的位置：
x x x o o
x o o o o
(此时已经放完 1~4， 5可能放在一排 4 列或者二排二列）

接下来就是怎么记录这种状态了。不难发现，我们可以用一个二元数对 (a, b) 来表示还未填充的位置的状态，其中 a 表示第一排的剩余空数，b 表示第二排的。以如上两个情形为例，情形一对应的状态就是 (3, 3)，情形 2 对应的状态就是 (2, 4)。注意， 根据规则，a <= b 总是成立的。
我们再以 f(a, b) 来表示 (a, b) 状态对应的可能的填充方式的总数，那么就会得到如下的递推公式：
（情形还是和上面保持一致）
情形 1: a = b
那么 f(a, b) = f(a - 1, b)
（也就是说你只能填一个位置）
情形 2: a < b
那么 f(a, b) = f(a - 1, b) + f(a, b - 1)
（也就是说你能填两个位置，第一行最左边的剩余位置，或者第二行最左边的剩余位置，填完后 分别对应 a - 1 和 b - 1，总方法数就是把这两个方法数加起来）
边界条件： f(0, 0) = 1, f(-1, ...) = f(..., -1) = 0
（即都填满后剩下 “唯一” 一种方案，即不填。对这种比较抽象的边界条件不太适应的同学，也可以手动补一些自己可以直观接受的边界条件，比如 f(1, 1) = f(0, 1) = f(0, 2) = ... f(0, 5) = 0）
这样 DP 的 complexity 就是 O(罐子^2)。这个题目里只有 10 个 罐子，还是比较好算的。当然，如果你有 1w 个罐子，分上下排成 5000, 5000 排，老夫的算法还是可以在 O(5000^2) 给出结果的，毫秒级！

老夫本想 coding 一下算出楼主的答案。但想想既然只是 O(25), 不妨来手推一下吧：
我们想求的是 f(5, 5)，那么依次计算即可：
f(0, 0) = 1
f(0, 1) = 1
f(1, 1) = 1
f(0, 2) = 1
f(1, 2) = f(0, 2) + f(1, 1) = 2
f(2, 2) = f(1, 2) = 2
f(0, 3) = 1
f(1, 3) = f(0, 3) + f(1, 2) = 3
f(2, 3) = f(1, 3) + f(2, 2) = 3 + 2 = 5
f(3, 3) = f(2, 3) = 5
f(0, 4) = 1
f(1, 4) = f(0, 4) + f(1, 3) = 4
f(2, 4) = f(1, 4) + f(2, 3) = 4 + 5 = 9
f(3, 4) = f(2, 4) + f(3, 3) = 9 + 5 = 14
f(4, 4) = f(3, 4) = 14
f(0, 5) = 1
f(1, 5) = f(0, 5) + f(1, 4) = 5
f(2, 5) = f(1, 5) + f(2, 4) = 5 + 9 = 14
f(3, 5) = f(2, 5) + f(3, 4) = 14 + 14 = 28
f(4, 5) = f(3, 5) + f(4, 4) = 28 + 14 = 42
f(5, 5) = f(4, 5) = 42

所以最终有 42 种方法！
我佬写着写着，总感觉这里面有个什么递推公式，所以或许可以直接列出式子而不是用DP 的方式来做状态递归（就好比斐波那契有个通项公式，而不需要用O(n) 的方式去算第 n 项一样）。但我佬的脑子不太够用了，留给后人继续深挖吧。
Q(n) = 1/n! * \prod_{i= n+2}^{2n} i
= 1/n! * (n+2)*(n+3)*...*(2n)
x1 图片
页首
头像
TheMatrix
论坛支柱
论坛支柱
2024年度优秀版主
TheMatrix 的博客
帖子互动： 264
帖子： 13266
注册时间： 2022年 7月 26日 00:35

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 TheMatrix »

lbs 写了： 2023年 1月 22日 00:04 口算不太会。不过这个问题用算法是可以做的。倒也不用暴力穷举（虽然总共就 10 个数，暴力穷举确实也能秒算）。其实可以用 DP 的思想。注意到这个条件限制实际是说：相邻的两个数，右边的总比左边大，下边的也总比上边的大。这个就构成了一个这十个位置的序关系（下面是个粗糙的示意图）：
1 -> 2 -> ...
| |
\/ \/
6 -> 7 -> ...

这个限制就决定了，1 只能在最左上角（因为没有再比它小的了）。为了知道总共有多少种方法，我们就考虑，依次把 1, 2, 3, ..., 10 放到十个位置里，能有多少种放法。放完 1 （必须在左上角）之后，再放 2 的位置，可以是上面示意图里 2 的位置，或者 6 的位置。以此类推。同时注意到，每次放置的时候，只能在图像中最左上的位置（可能有一个或两个 ）来放，分别对应如下的情形（下图中 x 表示已放置，o 表示未放置）：
1. 只有一个新的位置：
x x o o o
x x o o o
(此时已经放完 1~4， 5 只能放在第一排第三列）
2. 有两个新的位置：
x x x o o
x o o o o
(此时已经放完 1~4， 5可能放在一排 4 列或者二排二列）

接下来就是怎么记录这种状态了。不难发现，我们可以用一个二元数对 (a, b) 来表示还未填充的位置的状态，其中 a 表示第一排的剩余空数，b 表示第二排的。以如上两个情形为例，情形一对应的状态就是 (3, 3)，情形 2 对应的状态就是 (2, 4)。注意， 根据规则，a <= b 总是成立的。
我们再以 f(a, b) 来表示 (a, b) 状态对应的可能的填充方式的总数，那么就会得到如下的递推公式：
（情形还是和上面保持一致）
情形 1: a = b
那么 f(a, b) = f(a - 1, b)
（也就是说你只能填一个位置）
情形 2: a < b
那么 f(a, b) = f(a - 1, b) + f(a, b - 1)
（也就是说你能填两个位置，第一行最左边的剩余位置，或者第二行最左边的剩余位置，填完后 分别对应 a - 1 和 b - 1，总方法数就是把这两个方法数加起来）
边界条件： f(0, 0) = 1, f(-1, ...) = f(..., -1) = 0
（即都填满后剩下 “唯一” 一种方案，即不填。对这种比较抽象的边界条件不太适应的同学，也可以手动补一些自己可以直观接受的边界条件，比如 f(1, 1) = f(0, 1) = f(0, 2) = ... f(0, 5) = 0）
这样 DP 的 complexity 就是 O(罐子^2)。这个题目里只有 10 个 罐子，还是比较好算的。当然，如果你有 1w 个罐子，分上下排成 5000, 5000 排，老夫的算法还是可以在 O(5000^2) 给出结果的，毫秒级！

老夫本想 coding 一下算出楼主的答案。但想想既然只是 O(25), 不妨来手推一下吧：
我们想求的是 f(5, 5)，那么依次计算即可：
f(0, 0) = 1
f(0, 1) = 1
f(1, 1) = 1
f(0, 2) = 1
f(1, 2) = f(0, 2) + f(1, 1) = 2
f(2, 2) = f(1, 2) = 2
f(0, 3) = 1
f(1, 3) = f(0, 3) + f(1, 2) = 3
f(2, 3) = f(1, 3) + f(2, 2) = 3 + 2 = 5
f(3, 3) = f(2, 3) = 5
f(0, 4) = 1
f(1, 4) = f(0, 4) + f(1, 3) = 4
f(2, 4) = f(1, 4) + f(2, 3) = 4 + 5 = 9
f(3, 4) = f(2, 4) + f(3, 3) = 9 + 5 = 14
f(4, 4) = f(3, 4) = 14
f(0, 5) = 1
f(1, 5) = f(0, 5) + f(1, 4) = 5
f(2, 5) = f(1, 5) + f(2, 4) = 5 + 9 = 14
f(3, 5) = f(2, 5) + f(3, 4) = 14 + 14 = 28
f(4, 5) = f(3, 5) + f(4, 4) = 28 + 14 = 42
f(5, 5) = f(4, 5) = 42

所以最终有 42 种方法！
我佬写着写着，总感觉这里面有个什么递推公式，所以或许可以直接列出式子而不是用DP 的方式来做状态递归（就好比斐波那契有个通项公式，而不需要用O(n) 的方式去算第 n 项一样）。但我佬的脑子不太够用了，留给后人继续深挖吧。
赞。

dynamic programming的方法我一直没怎么用过。
页首
FGH
论坛精英
论坛精英
帖子互动： 101
帖子： 6927
注册时间： 2022年 7月 25日 16:30

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 FGH »

这是组合的杨表数。
https://en.wikipedia.org/wiki/Young_tableau
页首
Caravel
论坛元老
论坛元老
Caravel 的博客
帖子互动： 564
帖子： 24664
注册时间： 2022年 7月 24日 17:21

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 Caravel »

FGH 写了： 2023年 1月 22日 08:33 这是组合的杨表数。
https://en.wikipedia.org/wiki/Young_tableau
真的？杨表可以用来算群的不可约表象, 果真如此, 楼主要求的抽象找到了
页首
头像
TheMatrix
论坛支柱
论坛支柱
2024年度优秀版主
TheMatrix 的博客
帖子互动： 264
帖子： 13266
注册时间： 2022年 7月 26日 00:35

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 TheMatrix »

FGH 写了： 2023年 1月 22日 08:33 这是组合的杨表数。
https://en.wikipedia.org/wiki/Young_tableau
看了一下。完了，又有group representation。
页首
头像
YWY（夜未央）
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动： 1267
帖子： 13856
注册时间： 2022年 7月 22日 17:25

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 YWY（夜未央） »

（ヅ） 写了： 2023年 1月 22日 03:19 Q(n) = 1/n! * \prod_{i= n+2}^{2n} i
= 1/n! * (n+2)*(n+3)*...*(2n)
赞！至少对2，4，6，8，10，12是都成立。如此简单的公式，能找到其背后简明的逻辑就完美了。
持仓抄底锁利，你钱你定
看牛观猪喊熊，自娱自乐
股市变幻莫测，不作不死
赌途曲折无常，吃枣药丸
页首
Caravel
论坛元老
论坛元老
Caravel 的博客
帖子互动： 564
帖子： 24664
注册时间： 2022年 7月 24日 17:21

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 Caravel »

TheMatrix 写了： 2023年 1月 22日 11:04 看了一下。完了，又有group representation。
楼主是不是去什么趣味群论找来的题目，或者所有组合数学就是群论的初等版
页首
头像
（ヅ）
论坛支柱
论坛支柱
帖子互动： 544
帖子： 11677
注册时间： 2022年 8月 21日 14:20

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 （ヅ） »

YWY 写了： 2023年 1月 22日 11:06 赞！至少对2，4，6，8，10，12是都成立。如此简单的公式，能找到其背后简明的逻辑就完美了。
参考@lbs的思路用归纳法

把dp matrix Q写下来，
row 0:1 1 1 1 1 1....
row 1:0 1 2 3 4 5....
row 2:0 0 2 5 9 14 20 27 35
...
Q(i, j) = Q(i-1,j) + Q(i, j-1), j > i
Q(n,n) = Q(n-1,n)

能算出来
Q(0,j) = 1
Q(1, j) = j
Q(2, j) = 1/2 (j-1)(j+2)
Q(3, j) = 1/3! (j-2)(j+2)(j+3)
Q(4,j) = 1/4!(j-3)(j+2)(j+3)(j+4）

然后猜了这个公式
Q(n,j) = 1/n! (j-n+1)(j+2)(j+3)...(j+n)

用归纳法证明
页首
头像
TheMatrix
论坛支柱
论坛支柱
2024年度优秀版主
TheMatrix 的博客
帖子互动： 264
帖子： 13266
注册时间： 2022年 7月 26日 00:35

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 TheMatrix »

（ヅ） 写了： 2023年 1月 22日 12:14 参考@lbs的思路用归纳法

把dp matrix Q写下来，
row 0:1 1 1 1 1 1....
row 1:0 1 2 3 4 5....
row 2:0 0 2 5 9 14 20 27 35
...
Q(i, j) = Q(i-1,j) + Q(i, j-1), j > i
Q(n,n) = Q(n-1,n)

能算出来
Q(0,j) = 1
Q(1, j) = j
Q(2, j) = 1/2 (j-1)(j+2)
Q(3, j) = 1/3! (j-2)(j+2)(j+3)
Q(4,j) = 1/4!(j-3)(j+2)(j+3)(j+4）

然后猜了这个公式
Q(n,j) = 1/n! (j-n+1)(j+2)(j+3)...(j+n)

用归纳法证明
赞。DP真有用啊。
页首
头像
YWY（夜未央）
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动： 1267
帖子： 13856
注册时间： 2022年 7月 22日 17:25

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 YWY（夜未央） »

（ヅ） 写了： 2023年 1月 22日 12:14 参考@lbs的思路用归纳法

把dp matrix Q写下来，
row 0:1 1 1 1 1 1....
row 1:0 1 2 3 4 5....
row 2:0 0 2 5 9 14 20 27 35
...
Q(i, j) = Q(i-1,j) + Q(i, j-1), j > i
Q(n,n) = Q(n-1,n)

能算出来
Q(0,j) = 1
Q(1, j) = j
Q(2, j) = 1/2 (j-1)(j+2)
Q(3, j) = 1/3! (j-2)(j+2)(j+3)
Q(4,j) = 1/4!(j-3)(j+2)(j+3)(j+4）

然后猜了这个公式
Q(n,j) = 1/n! (j-n+1)(j+2)(j+3)...(j+n)

用归纳法证明
我对DP不懂，所以不敢用。比如，这个Q(i, j)到底代表什么？能不能用Q(1, 2)为例，解释一下Q(1, 2)代表什么？为什么Q(1, 2) = 2？
持仓抄底锁利，你钱你定
看牛观猪喊熊，自娱自乐
股市变幻莫测，不作不死
赌途曲折无常，吃枣药丸
页首
头像
（ヅ）
论坛支柱
论坛支柱
帖子互动： 544
帖子： 11677
注册时间： 2022年 8月 21日 14:20

Re: 解题了解题了，蜂蜜罐子排列

帖子 由 （ヅ） »

YWY 写了： 2023年 1月 22日 13:59 我对DP不懂，所以不敢用。比如，这个Q(i, j)到底代表什么？能不能用Q(1, 2)为例，解释一下Q(1, 2)代表什么？为什么Q(1, 2) = 2？
Q(i,j):= f(i,j) (根据上面lbs的分析)
我们可以用一个二元数对 (a, b) 来表示还未填充的位置的状态，其中 a 表示第一排的剩余空数，b 表示第二排的。以如上两个情形为例，情形一对应的状态就是 (3, 3)，情形 2 对应的状态就是 (2, 4)。注意， 根据规则，a <= b 总是成立的。
我们再以 f(a, b) 来表示 (a, b) 状态对应的可能的填充方式的总数，那么就会得到如下的递推公式：
页首
回复

回到 “STEM”