算法笔试模拟题精解之“难住Tom 的问题”

算法笔试模拟题精解之“难住 Tom 的问题”

贡献者 | 猿圈

简介：拿样例来说 2 3 100, 说明有 3 个桶，第 0 个桶一定是空的，那么符合条

件的有 12 种方案，我们需要从中推出转移方程。

题目描述

等级：困难

知识点：DP

查看题目：难住 Tom 的问题

Jerry 和 Tom 在公园里感到很无聊，于是就开始研究起来题目了，Jerry 有一个

n+1 个桶 (1<=n<=300)，这些桶的编号为 0,1,2,...,n，然后让 Tom 去构造这些桶

( 每个桶可以看作 list)，必须要满足以下的三个要求：

1. 对于第 i 个桶里，它里面有 i 个数 ai，并且这些数不能大于 x(1<=ai<=300)。
2. 对于第 i-1 个桶，它必须是第 i 个桶的子序列。
3. 对于第 i 个桶，它的字典序要大于第 i-1 个桶。

问满足以上要求的方案有多少总，答案对 y(2<=y<=1e9) 取模。

输入三行数据，分别为 n,x,y，意思同题意。

输出一个数，表示最终的方案数，答案对 y 取模。

示例 1

输入：

3

100

输出：

12

解题方法：

拿样例来说 2 3 100, 说明有 3 个桶，第 0 个桶一定是空的，那么符合条件的有

以下 12 种方案：

({0},{1},{1,1}),

({0},{1},{1,2}),

({0},{1},{1,3}),

({0},{1},{2,1}),

({0},{1},{3,1}),

({0},{2},{2,1}),

({0},{2},{2,2}),

({0},{2},{3,1}),

({0},{3},{3,1}),

({0},{3},{3,2}),

({0},{3},{3,3})，

这只是简单的列举出了所有的情况，我们需要从中推出转移方程。

以 {0},{2} 为例，要构造出第三个桶就相当于往第二个桶中插入一个数字；

那么如果这个数字插在 2 的左边，一定是要比 2 大的数才可以，如果插到右边

对于这个情况来说没有限制条件，如果对于位数较多的数列来说也要考虑到字典序

的因素。

所以我们考虑 fi[p] 中，i 表示当前的长度，j 表示取到的数字，p 表示有 p 个位置

可插。

一共有三种状态，当你的 p 没位置了就没有地方可插，那么这个数就不插了

dpi[i] += dpi[p], 这里的第三维为 i 是因为所有的数都比 j+1 小，所以插到哪里都是可

以的，所以为 i。

如果 p 不为 0 的话说明有地方可插，这时可以考虑插在这个地方或者不插这个地

方，如果不插这个地方 dpi[p-1]+=dpi[p]，如果插这个地方 dpi+1[p]+=dpi[p]，这里

还需要乘以 p+1 是因为还有 p 个位置。

时间复杂度：O(n^3)

空间复杂度：n^3

看完之后是不是有了答题思路了呢，快来练练手吧：难住 Tom 的问题