P3430. 书籍叠放

解题思路

注意：本题和 俄罗斯套娃信封问题、面试题 17.08. 马戏团人塔、无矛盾的最佳球队 等题目几乎完全一致，属于 最长递增子序列 的轻变形题目。

如何转变为 LIS 问题

长度严格不等的情况

先考虑一种比较简单的情况，所有书本的长度两两不等，例如用例：

我们可以把所有书本按照长度进行排列，得到：

对 books 进行排序后，单看长度的话，后面位置的书本长度一定大于前面位置的书本长度，即一定存在 books[i][0] > books[j][0] 对于任何 i > j 成立。故我们只需要考虑宽度即可，把所有宽度从 books 数组中提取出来可以得到宽度数组 widths：

为了使得叠放的书本尽可能多，子序列就要尽可能长。问题实际上转变为对宽度数组 widths 考虑 最长递增子序列（LIS） 问题，即宽度数组能够取得的 LIS 长度，就是整个书本数组能够取得的 LIS 长度。故我们对 widths 数组进行 LIS 问题的求解即可。

上述例子可以得到 widths 的 LIS 是 [1, 2, 3]，对应 books 的 LIS 是 [(1, 1), (3, 2), (4, 3)]，长度 3 即为答案。

长度可能相等的情况

对于书本长度可能相等的情况呢？考虑用例：

如果我们考虑对长度进行升序排序后，对长度相等的书本根据宽度也进行升序排序，那么会得到：

提取宽度数组 widths 得到：

显然此时 widths 的 LIS 是 [1, 2, 3, 4]，长度为 4，但其对应的 books 数组的 LIS 并不能取 [(1, 1), (2, 2), (2, 3), (4, 4)]，因为长度同样为 2 的书本的叠放并不符合要求。

为了避免上述问题，我们考虑对长度进行升序排序后，对长度相等的书本根据宽度进行 降序 排序，那么会得到：

提取宽度数组 widths 得到：

此时 widths 的 LIS 是 [1, 3, 4] 或者 [1, 2, 4]，对应的 books 数组的 LIS 为 [(1, 1), (2, 3), (4, 4)] 或者 [(1, 1), (2, 2), (4, 4)]，符合要求。

这是因为对于长度相等的书本而言，更小的宽度被排到更后的位置，这样当我们对宽度考虑 LIS 问题时，就不会出现长度相等的书籍出现在递增子序列中的情况了。

排序依据

故最终我们选择 先依据长度升序，再依据宽度降序 的方式，对书本数组 books 进行排序：

dp 求解 LIS 问题

在对书本数组进行排序之后，剩下部分就是对所有书本宽度做常规的 LIS 问题了，此部分可以参考 最长递增子序列。

我们考虑动态规划三部曲：

dp 数组的含义是什么？

dp 数组是一个长度为 n 的一维列表，dp[i] 表示 以第 i 本书籍为结尾的最长递增子序列的长度。

动态转移方程是什么？

对于第 i 本书，我们都去考虑其前面的第 i-1 本书，用索引 j 表示。如果第 i 本书的宽度大于第 j 本书的宽度，即存在 books[i][1] > books[j][1] 成立，那么 i 可能可以放在 j 的后面。 如果选择 i 放在 j 的下方能使得 i 叠放更多书籍，或者说递增子序列能够更长，那么我们选择 j。

dp 数组如何初始化？

以第 0 本书为结尾的最长递增子序列的长度为 1。其余书本对应的最长递增子序列长度也可以默认为 1。

PS：这类 LIS 问题还存在更加优秀的时间复杂度为 O(n log n) 的 贪心 + 二分 解法，但已经有点超纲。对于 OD 考试而言，时间复杂度为 O(n²) 的 dp 解法已经完全够用。 具体可详见文档 再论 LIS 问题：贪心 + 二分算法。

代码

解法一：DP