1. 从“友好城市”这道题看动态规划的区间建模思路第一次看到“友好城市”这个标题很多人会以为是一道图论题或者是一道并查集题目。实际上这是一道非常经典的线性动态规划问题核心考点是**最长上升子序列LIS**的变种。题目背景大致是这样的一条河的两岸各有若干座城市北岸城市和南岸城市之间存在若干条“友好关系”航线每条航线连接南北两岸各一座城市。现在要求选出尽可能多的航线使得任意两条航线之间不会交叉。问最多能选出多少条航线。这道题之所以经典是因为它把一个看似几何的问题转化成了一个纯粹的序列问题。转化的关键就在于排序加LIS。如果你之前做过“导弹拦截”或者“最长上升子序列”的模板题这道题本质上就是加了一个排序预处理。但如果你没做过第一次接触很容易陷入“怎么判断交叉”的几何思维里出不来。我当年第一次做这道题的时候花了将近四十分钟才想明白为什么要排序。后来带别人刷题发现大家卡住的地方几乎一模一样知道要用LIS但不知道怎么把“不相交”这个条件翻译成LIS能处理的形式。所以这篇博文我打算把这道题从建模到实现到边界处理完整地拆一遍。适合已经了解LIS基本写法、但遇到变形题容易卡壳的读者也适合想重新梳理区间DP建模思路的朋友。2. 问题建模为什么排序之后就能变成LIS2.1 交叉条件的数学表达先把问题抽象一下。假设北岸城市用坐标表示南岸城市也用坐标表示。为了方便我们把北岸城市按位置从左到右编号南岸城市也按位置从左到右编号。每一条友好航线可以表示成一个点对 ((x, y))其中 (x) 是北岸城市编号(y) 是南岸城市编号。现在考虑两条航线 ((x_1, y_1)) 和 ((x_2, y_2))。它们不相交的条件是什么画个图就能看出来如果 (x_1 x_2)那么必须要有 (y_1 y_2)否则两条线就会交叉。反过来如果 (x_1 x_2)则必须 (y_1 y_2)。换句话说两条航线不相交当且仅当两个点对的大小关系一致。这个条件用数学语言说就是对于任意两条选中的航线要么 (x) 和 (y) 同时递增要么同时递减。但因为我们选的是一个集合集合内的元素可以按 (x) 排序排序之后只需要保证 (y) 也是递增的即可。这就是为什么排序之后问题会变成LIS。2.2 排序策略的选择这里有一个细节按什么排序如果按北岸城市编号 (x) 升序排序那么排序之后只需要在 (y) 序列上求最长上升子序列。如果按 (x) 降序排序那就求最长下降子序列本质上是一样的。但要注意一种特殊情况如果两个航线的 (x) 相同怎么办在实际题目中通常不会出现同一个北岸城市连接多个南岸城市的情况因为那样的话两条航线必然交叉它们共享同一个起点。但有些变种题目可能会出现这时候需要特殊处理。标准做法是如果 (x) 相同按 (y) 降序排序这样在求LIS的时候不会同时选中两个 (x) 相同的元素。这个技巧在“俄罗斯套娃信封”那道题里也用到过属于区间DP的常见套路。我个人的习惯是统一按 (x) 升序、(y) 降序排序然后直接跑LIS。这样写起来最省心不用分情况讨论。2.3 为什么不能用贪心有人可能会想能不能用贪心比如每次选一条航线然后删掉所有与它交叉的航线重复这个过程。这个思路看起来合理但实际上不对。举个简单的例子假设有三条航线 ((1, 3), (2, 1), (3, 2))。如果先选 ((1, 3))那么 ((2, 1)) 和 ((3, 2)) 都和它交叉只能选一条总共选两条。但如果选 ((2, 1)) 和 ((3, 2))这两条不交叉也是两条。贪心在这个例子里恰好能得到最优解但换一个例子就不行了。考虑 ((1, 2), (2, 3), (3, 1))。贪心如果先选 ((1, 2))然后只能再选 ((2, 3))总共两条。但如果选 ((2, 3)) 和 ((3, 1))也是两条。再换一个((1, 4), (2, 1), (3, 2), (4, 3))。贪心选 ((1, 4)) 之后只能选一条总共两条但最优解是选 ((2, 1), (3, 2), (4, 3))总共三条。所以贪心是错的必须用DP。这个反例我经常用来提醒自己区间选点类问题只要涉及“不相交”约束优先考虑排序加LIS不要凭直觉贪心。3. LIS的两种写法与选择建议3.1 朴素O(n²)写法LIS最朴素的写法是定义 (dp[i]) 表示以第 (i) 个元素结尾的最长上升子序列长度。转移方程是[ dp[i] \max_{j i, a[j] a[i]} dp[j] 1 ]最终答案是 (\max dp[i])。这种写法时间复杂度是 (O(n^2))空间复杂度是 (O(n))。对于“友好城市”这道题如果城市数量在几千以内这个写法完全够用。而且它有一个好处可以顺便记录方案如果需要输出具体选了哪些航线用这个写法更容易回溯。我一般建议新手先用这个写法把题目过了再去优化。因为 (O(n^2)) 的写法逻辑直观不容易写错边界。3.2 二分优化O(n log n)写法如果城市数量达到十万级别(O(n^2)) 就会超时这时候需要用二分优化。优化的思路是维护一个数组 (tails)其中 (tails[i]) 表示长度为 (i1) 的上升子序列的最小结尾元素。遍历原数组时对于每个元素用二分查找在 (tails) 中找到第一个大于等于它的位置替换掉那个元素如果找不到就追加到末尾。这个写法的核心在于 (tails) 数组是单调递增的所以可以二分。最终 (tails) 的长度就是LIS的长度。但要注意(tails) 数组本身并不是LIS它只是用来计算长度的。如果需要输出方案还得额外记录前驱。两种写法的对比如下写法时间复杂度空间复杂度是否方便输出方案适用场景朴素DPO(n²)O(n)方便n ≤ 5000二分优化O(n log n)O(n)需额外记录n 较大我个人的习惯是如果题目不要求输出方案直接用二分优化如果要求输出方案用朴素DP加前驱数组。这道“友好城市”通常只要求输出最大数量所以二分优化是首选。3.3 二分查找的边界细节二分优化里最容易写错的地方是二分查找的边界。标准写法是找第一个大于等于当前元素的位置用lower_bound。但有些题目要求严格上升有些允许非严格上升即不下降。这两者的区别在于严格上升用lower_bound非严格上升用upper_bound。在“友好城市”里航线之间不能交叉等价于 (y) 严格递增所以用lower_bound。如果题目改成“航线可以共线但不交叉”那就可能允许相等需要用upper_bound。这个细节我踩过坑有一次比赛里题目描述模糊我默认用了lower_bound结果WA了两发后来发现题目允许两条航线共享端点应该用upper_bound。提示写二分优化LIS时先确认题目要求的是严格上升还是非严格上升再决定用lower_bound还是upper_bound。这个选择直接影响结果。4. 完整实现与代码拆解4.1 输入处理与排序假设输入格式是第一行一个整数 (n)表示航线数量接下来 (n) 行每行两个整数 (x, y)表示一条航线连接北岸城市 (x) 和南岸城市 (y)。我们需要先读取所有航线然后按 (x) 升序、(y) 降序排序。排序的代码用Python写大概是routes [] for _ in range(n): x, y map(int, input().split()) routes.append((x, y)) routes.sort(keylambda t: (t[0], -t[1]))这里-t[1]表示按 (y) 降序。如果题目保证 (x) 不重复其实按 (x) 升序就够了但加上 (y) 降序更保险。4.2 提取y序列并求LIS排序之后把所有 (y) 提取出来组成一个数组然后对这个数组求LIS。用二分优化的写法import bisect ys [y for _, y in routes] tails [] for y in ys: pos bisect.bisect_left(tails, y) if pos len(tails): tails.append(y) else: tails[pos] y print(len(tails))这段代码非常短但每一行都有讲究。bisect_left找的是第一个大于等于 (y) 的位置保证严格上升。如果换成bisect_right就变成非严格上升了。4.3 朴素DP写法对照如果用朴素DP代码稍微长一点但逻辑更直观ys [y for _, y in routes] n len(ys) dp [1] * n for i in range(n): for j in range(i): if ys[j] ys[i]: dp[i] max(dp[i], dp[j] 1) print(max(dp))这段代码的时间复杂度是 (O(n^2))在 (n) 较小的时候完全没问题。我建议初学者先用这个写法把样例过了再改成二分优化这样能更深刻地理解LIS的本质。4.4 一个完整的测试案例假设输入是4 1 3 2 1 3 2 4 4排序后还是这个顺序因为 (x) 已经升序。(y) 序列是[3, 1, 2, 4]。对这个序列求LIS最长上升子序列是[1, 2, 4]长度是3。所以答案是3。验证一下选航线 ((2,1), (3,2), (4,4))三条航线互不交叉。如果选 ((1,3)) 和 ((4,4))只有两条。所以3是最优解。这个案例我经常用来给别人演示因为它足够小手算就能验证而且能直观看到排序后的效果。5. 常见错误与排查清单5.1 排序方向搞反最常见的错误是把 (y) 也按升序排序或者排序时忘了处理 (x) 相同的情况。如果 (x) 相同且 (y) 升序那么在求LIS时可能会同时选中两个 (x) 相同的航线导致答案偏大。这个错误在样例上不一定能发现因为样例通常不会构造 (x) 相同的边界情况。排查方法自己构造一组 (x) 相同的测试数据比如3 1 1 1 2 1 3正确答案应该是1因为同一个北岸城市只能选一条航线。如果代码输出3说明排序策略有问题。5.2 二分查找用错函数前面提到过严格上升用bisect_left非严格上升用bisect_right。如果题目要求严格上升但用了bisect_right答案会偏大。这个错误在随机数据上很难发现因为随机数据里相等元素很少。但在构造数据上比如 (y) 序列全是相同值就能立刻暴露。排查方法构造一组 (y) 全部相同的测试数据比如3 1 1 2 1 3 1正确答案是1因为 (y) 相同意味着航线交叉。如果代码输出3说明二分函数用错了。5.3 忘记处理空输入有些题目可能给出 (n0) 的情况这时候直接输出0。如果代码里没有特判可能会在排序或求LIS时出错。虽然大多数题目不会这么坑但加上特判不亏。5.4 常见问题速查表问题现象可能原因排查方法答案偏大排序时 (y) 升序或二分用了bisect_right构造 (x) 相同或 (y) 相同的测试数据答案偏小排序时 (x) 降序但没调整LIS方向检查排序后是否按 (x) 升序运行超时用了 (O(n^2)) 写法但 (n) 很大改成二分优化输出为0没有处理 (n0) 或输入读取失败加特判并检查输入格式注意这道题的输入规模通常不会特别大但如果你在比赛里遇到变种题一定要先看数据范围再决定用哪种写法。数据范围是选择算法的第一依据。6. 从这道题延伸出去的几个变种6.1 带权版本如果每条航线有一个“友好度”权重要求选出的航线不相交且总权重最大那就变成了带权LIS问题。这时候不能用二分优化只能用朴素DP或者树状数组优化。转移方程变成[ dp[i] w[i] \max_{j i, a[j] a[i]} dp[j] ]这个变种在竞赛里出现过难度比原题高不少。如果原题做熟了可以拿这个变种练手。6.2 三维版本如果城市分布在三维空间里航线是三维空间中的线段要求选出的线段两两不相交那就变成了三维偏序问题。这时候需要CDQ分治或者树套树难度直接上了一个台阶。不过这种变种已经超出了“友好城市”原题的范畴属于进阶内容。6.3 输出具体方案如果题目要求输出选了哪些航线就需要在DP过程中记录前驱。朴素DP写法加一个pre数组即可二分优化写法需要额外维护每个元素在tails中的位置和前驱稍微麻烦一点。我一般建议这种情况下直接用朴素DP代码可读性更好。6.4 与“导弹拦截”的对比“导弹拦截”那道题求的是最长不上升子序列和这道题求最长上升子序列是对偶的。两道题的建模思路几乎一样都是排序加LIS。区别在于“导弹拦截”通常不需要排序直接对原序列求LIS即可。把这两道题放在一起做能更好地理解LIS的变形。我个人刷题的体会是LIS类问题的核心不在于LIS本身而在于如何把原问题转化为LIS。排序是转化的关键手段而排序策略的选择取决于题目对“不相交”或“不重叠”的定义。把这个逻辑想清楚这一类题就都能拿下。7. 实操建议与刷题路线如果你刚开始接触这类问题我建议按这个顺序刷先做纯LIS模板题把朴素写法和二分写法都手写一遍确保能默写出来。再做“友好城市”重点体会排序加LIS的转化过程。然后做“导弹拦截”对比最长上升和最长不上升的区别。最后做“俄罗斯套娃信封”这道题涉及二维排序加LIS是“友好城市”的进阶版。每道题做完之后不要只看AC要自己构造几组边界数据测试。比如全相同、全递增、全递减、(n1)、(n0) 这些情况。我见过太多人模板题AC了但边界数据一测就挂原因就是没养成构造测试数据的习惯。另外写二分优化LIS的时候建议把bisect_left和bisect_right的区别记牢。如果记不住就记一句话严格上升找左边界非严格上升找右边界。这句话我用了好几年从来没记混过。最后分享一个我自己的小习惯每次写完LIS代码都会用一组随机数据和暴力 (O(n^2)) 对拍。对拍能发现很多肉眼看不出来的边界问题尤其是二分查找的边界。这个方法虽然笨但确实有效。