题目描述

参见原题链接

样例

参加原题链接

算法1

(动态规划/状态空间搜索) $O(n^2)$

把每一个信封看作一个节点，如果信封a可以放进信封b，则连一条a到b的有向边。因为“可以放进”关系决定边长单调递减，所以建成的图是有向无回路图。问题转换为有向无回路图上的最长路径，典型的dp问题，可以用记忆化搜索实现。
时间复杂度分析：
n个点，每个点尝试$n - 1$个其他点是否可达，复杂度 $O(n^2)$

C++ 代码

算法2

转换为最长上升子序列

最长上升子序列问题可以重新描述为：给定一个点的集合，每个点有两个属性，在序列中的index i和值 val；定义集合中两个点的序关系n1 < n2当且仅当n1.index < n2.index && n1.val < n2.val;求集合的最大全序子集（注意到最长上升子序列问题中index和val的地位是对称）。现在把信封的x或y中一者当作index，另一者做val，这几乎就是最长上升子序列问题，唯一的区别在于，同一个x可能有多个不同y的信封，而序列中同一个index只有一个val。为了解决这个问题，对x相同的点按y的逆序排序，显然这个新的排序不会引入多余的小于关系。

时间复杂度分析：

C++ 代码