1. 从“友好城市”这道题看动态规划的区间建模思路第一次看到“友好城市”这个标题很多人会以为是一道图论题或者并查集题毕竟“城市”和“友好”两个词很容易让人联想到连通性、配对关系。但真正做过这道题的人都知道它本质上是一道披着应用题外衣的最长上升子序列问题也就是经典的LIS模型。这个判断非常关键因为它决定了你后面所有的建模方向——如果你往图论方向想可能会陷入建图、找环、拓扑排序的泥潭而一旦识别出LIS的本质整道题的难度会瞬间下降一个档次。这道题的核心场景是这样的一条河将城市分为南北两岸北岸有n个城市南岸也有n个城市每个北岸城市最多只能和南岸的一个城市建立友好关系而且航线不能交叉。问最多能建立多少对友好城市关系。这个“航线不能交叉”的约束就是整道题从普通配对问题升级为动态规划问题的关键所在。为什么“航线不交叉”这么重要你可以这样理解假设北岸城市按位置从左到右编号为1到n南岸城市也按位置从左到右编号。如果北岸的i城市连接了南岸的a城市北岸的j城市连接了南岸的b城市且i小于j那么航线不交叉的条件就是a必须小于b。换句话说北岸城市的顺序和南岸配对城市的顺序必须保持一致。这就把问题转化成了给定一组配对关系找出最长的子序列使得北岸城市递增的同时南岸城市也递增。这个转化过程是整道题最精妙的地方。很多初学者在这里卡住是因为他们没有意识到“不交叉”这个几何约束可以等价转化为“顺序一致”的代数约束。一旦完成了这个转化剩下的就是标准的LIS求解了。这道题适合谁来学习我认为它非常适合已经掌握了LIS基本解法但还不太会做模型转化的同学。因为LIS本身的DP解法并不复杂但“友好城市”这道题的价值在于教你如何从实际问题中抽象出LIS模型。这种建模能力才是算法竞赛中真正拉开差距的地方。另外这道题也适合作为区间DP和排序预处理的入门练习因为它涉及到了排序和LIS两个知识点的结合。2. 核心细节解析与建模要点2.1 为什么排序是解题的第一步拿到这道题第一反应应该是把北岸城市按位置排序。为什么因为题目给出的输入顺序可能是乱的而航线不交叉的约束是建立在位置顺序上的。如果你不排序就无法保证你处理的配对关系是按照北岸城市从左到右的顺序排列的。具体来说假设输入给出了若干对友好城市关系每对包含一个北岸城市编号和一个南岸城市编号。你需要先按照北岸城市编号从小到大排序。排序之后你得到的序列中北岸城市是递增的那么问题就变成了在这个序列中找出南岸城市编号的最长上升子序列。这里有一个细节需要注意题目中北岸城市和南岸城市的编号都是1到n而且每个城市最多只能连接一个对岸城市。这意味着排序之后北岸城市编号是严格递增的不会出现重复。这个性质保证了我们后续LIS求解的正确性。注意如果题目允许一个城市连接多个对岸城市那么排序后北岸城市编号可能出现重复这时候就需要额外处理。但本题中每个城市最多连接一个所以排序后北岸编号严格递增可以直接对南岸编号求LIS。2.2 LIS的两种解法选择排序完成后问题就变成了求南岸城市编号序列的最长上升子序列。LIS有两种经典解法一种是O(n²)的动态规划另一种是O(n log n)的贪心加二分。对于这道题来说n的范围通常不会特别大O(n²)的解法完全够用。但如果你想提升自己的算法能力我建议两种方法都实现一遍。O(n²)的解法更直观适合理解LIS的本质O(n log n)的解法更高效适合在实际比赛中使用。O(n²)解法的核心思想是定义dp[i]为以第i个元素结尾的最长上升子序列长度。状态转移方程是dp[i] max(dp[j]) 1其中j i且a[j] a[i]。这个方程的意思是如果前面的某个元素比当前元素小那么就可以接在它后面形成一个更长的上升子序列。O(n log n)解法的核心思想是维护一个数组tails其中tails[i]表示长度为i1的上升子序列的最小结尾元素。遍历原序列时对于每个元素用二分查找在tails中找到第一个大于等于它的位置替换掉那个位置的元素。如果找不到这样的位置就把它追加到tails末尾。最终tails的长度就是LIS的长度。这两种解法各有优劣。O(n²)的解法代码简单容易调试适合初学者O(n log n)的解法效率高但二分查找的边界条件容易写错需要仔细处理。2.3 边界条件与特殊情况的处理在实际写代码的时候有几个边界条件需要特别注意。第一个是n0的情况。虽然题目通常不会给出n0的测试数据但严谨的代码应该处理这种情况直接输出0即可。第二个是所有南岸城市编号都相同的情况。这时候LIS的长度是1因为严格上升子序列不能包含相等的元素。如果你的代码在判断上升条件时用了小于等于就会得到错误的结果。第三个是南岸城市编号完全逆序的情况。这时候LIS的长度也是1因为没有任何一对元素满足上升条件。这种情况可以用来测试你的代码是否正确处理了“不接在任何元素后面”的情况。提示在写LIS的O(n²)解法时初始化dp数组全部为1而不是0。因为每个元素本身至少可以构成一个长度为1的上升子序列。这个细节看似简单但很多人在紧张的时候会忘记。3. 完整实操过程与代码实现3.1 数据读取与预处理首先我们需要读取输入数据。题目通常会先给出一个整数n表示城市的数量然后给出n行每行两个整数分别表示一对友好城市的北岸编号和南岸编号。读取数据后我们需要把这些配对存储起来然后按照北岸城市编号排序。在C中可以用pair或者结构体来存储然后用sort函数排序。在Python中可以用列表存储元组然后用sort方法排序。排序之后我们只需要提取南岸城市的编号形成一个序列然后对这个序列求LIS。#include iostream #include algorithm using namespace std; const int N 5010; pairint, int cities[N]; int a[N], dp[N]; int main() { int n; cin n; for (int i 0; i n; i) { cin cities[i].first cities[i].second; } sort(cities, cities n); for (int i 0; i n; i) { a[i] cities[i].second; } // 接下来对a数组求LIS int ans 0; for (int i 0; i n; i) { dp[i] 1; for (int j 0; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } cout ans endl; return 0; }上面这段代码是O(n²)的LIS解法。它的逻辑非常清晰外层循环遍历每个元素内层循环遍历它之前的所有元素如果发现前面的元素比当前元素小就尝试更新dp[i]。最后答案就是dp数组中的最大值。3.2 O(n log n)解法的实现细节如果你想让代码更高效可以用O(n log n)的解法。这种解法的核心是维护一个tails数组并且用二分查找来更新它。#include iostream #include algorithm #include vector using namespace std; const int N 5010; pairint, int cities[N]; int main() { int n; cin n; for (int i 0; i n; i) { cin cities[i].first cities[i].second; } sort(cities, cities n); vectorint tails; for (int i 0; i n; i) { int x cities[i].second; auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } cout tails.size() endl; return 0; }这段代码的关键在于lower_bound的使用。lower_bound返回的是第一个大于等于x的位置。如果找到了这样的位置就用x替换掉它如果没找到说明x比tails中所有元素都大直接追加到末尾。这样维护的tails数组始终是严格上升的而且它的长度就是LIS的长度。注意这里用的是lower_bound而不是upper_bound因为我们要找的是严格上升子序列。如果题目要求的是非严格上升子序列允许相等那就应该用upper_bound。这个区别非常关键写错的话会导致答案偏大。3.3 参数计算与复杂度分析对于O(n²)的解法时间复杂度是O(n²)空间复杂度是O(n)。当n5000时n²25,000,000这个计算量在现代计算机上大约需要0.1秒左右完全可以在1秒的时间限制内完成。对于O(n log n)的解法时间复杂度是O(n log n)空间复杂度是O(n)。当n5000时n log n大约等于5000乘以12也就是60,000次操作比O(n²)快了三个数量级。如果n的范围扩大到10^5甚至10^6O(n log n)的解法依然能够轻松应对。在实际比赛中如果题目没有明确给出n的范围我通常会优先选择O(n log n)的解法因为它更保险。但如果n的范围很小比如n≤1000用O(n²)的解法反而更不容易出错因为二分查找的边界条件容易写错。3.4 测试用例验证为了验证代码的正确性我们可以构造几个测试用例。测试用例1n3配对关系为(1,2), (2,1), (3,3)。排序后南岸序列为2,1,3。LIS为2可以是2,3或者1,3。正确答案是2。测试用例2n4配对关系为(1,4), (2,3), (3,2), (4,1)。排序后南岸序列为4,3,2,1。LIS为1。正确答案是1。测试用例3n5配对关系为(1,1), (2,2), (3,3), (4,4), (5,5)。排序后南岸序列为1,2,3,4,5。LIS为5。正确答案是5。这三个测试用例覆盖了LIS的三种典型情况部分上升、完全下降、完全上升。如果你的代码能正确输出2、1、5那么基本逻辑就是正确的。4. 常见问题与排查技巧实录4.1 排序后忘记提取南岸序列这是初学者最容易犯的错误。有些人排序之后直接在原数组上做LIS但原数组是pair类型的比较的是first和second的组合而不是单纯的second。这样得到的LIS长度可能不对。正确的做法是排序后单独提取出second组成一个新的数组然后对这个数组求LIS。这个步骤虽然简单但在紧张的比赛环境中很容易被忽略。4.2 二分查找的边界条件写错在使用O(n log n)解法时lower_bound和upper_bound的选择非常关键。如果你不小心用了upper_bound那么当序列中存在相等元素时你会把它们当作上升的一部分导致LIS长度偏大。举个例子假设南岸序列是1,2,2,3。正确的LIS长度是31,2,3但如果你用upper_bound可能会得到4因为你会把两个2都算进去。这个错误在测试用例中不一定能发现因为很多题目的测试数据可能不包含重复元素。但一旦遇到重复元素就会出错。提示在写二分查找的时候建议先用小规模数据手动模拟一遍确认边界条件正确后再提交。这个习惯能帮你省下很多调试时间。4.3 数组大小开小了这道题中n的范围通常是5000左右所以数组开到5010就够了。但有些题目可能会把n的范围设得更大比如10^5。如果你按照5000来开数组就会导致数组越界程序崩溃或者得到错误结果。我的建议是在不确定n的范围时先看一下题目的数据范围说明。如果找不到就按照最坏情况来开数组比如开到10^6。多开一点空间不会影响程序的正确性但开小了会导致严重的运行时错误。4.4 常见问题速查表问题现象可能原因排查方法解决方案答案偏小排序后没有提取南岸序列检查LIS操作的对象单独提取second组成新数组答案偏大二分查找用了upper_bound检查二分函数的选择改用lower_bound程序崩溃数组大小不足检查n的范围增大数组容量答案错误dp数组初始化错误检查dp初始值全部初始化为1部分测试点超时用了O(n²)解法但n很大分析时间复杂度改用O(n log n)解法4.5 独家避坑技巧第一个技巧是在排序之前先检查输入数据中是否有重复的北岸城市编号。虽然题目通常保证每个城市最多连接一个对岸城市但如果你不确定可以先做一次去重或者检查。这个步骤能帮你避免一些奇怪的边界情况。第二个技巧是在写O(n log n)解法时可以用一个辅助函数来封装二分查找的逻辑这样主循环会更清晰也更容易调试。比如你可以写一个int findPosition(vectorint tails, int x)函数专门负责返回第一个大于等于x的位置。第三个技巧是在提交之前用随机数据生成器生成几组小规模测试数据然后用暴力解法比如枚举所有子序列来验证你的答案。这种方法虽然麻烦但能发现很多隐藏的逻辑错误。特别是对于LIS这种边界条件较多的算法暴力验证非常有必要。第四个技巧是如果你在比赛中遇到了类似的“配对不交叉”问题可以先尝试把问题转化为LIS模型。转化的关键是找到两个维度上的单调性约束。在这道题中北岸位置和南岸位置就是两个维度不交叉要求它们同向单调。这种建模思路在区间调度、任务安排等问题中也非常常见。5. 从这道题延伸出的算法思维5.1 区间建模与偏序关系“友好城市”这道题的本质是二维偏序问题。每个友好城市对可以看作一个点(x, y)其中x是北岸位置y是南岸位置。航线不交叉的条件等价于选出的点集中x和y都严格递增。这就是一个典型的二维偏序最长链问题。对于二维偏序问题通用的解法是先按一维排序然后在另一维上求LIS。这个思路可以推广到很多类似的问题中。比如“俄罗斯套娃信封”问题就是先按宽度排序然后在高度上求LIS。再比如“最长数对链”问题也是类似的思路。掌握了这个建模方法你就能解决一大类看起来不同但本质相同的问题。这种举一反三的能力比单纯会做一道题重要得多。5.2 排序预处理的作用在这道题中排序预处理起到了降维的作用。原本问题有两个维度北岸位置和南岸位置。通过排序我们把北岸位置这个维度固定住了变成了递增的顺序然后只需要在南岸位置上求LIS。这样就把二维问题降成了一维问题。这种“排序降维”的技巧在算法竞赛中非常常见。比如在计算几何中我们经常先按x坐标排序然后处理y坐标在区间问题中我们经常先按左端点排序然后处理右端点。排序的本质是引入一个顺序让我们可以按照这个顺序逐步处理问题而不需要考虑所有可能的组合。5.3 动态规划与贪心的选择LIS问题有两种解法动态规划和贪心加二分。这两种解法代表了两种不同的算法思维。动态规划的思路是考虑所有可能的子问题然后从中选择最优的。这种思路的优点是直观、容易理解缺点是效率可能不高。在LIS问题中O(n²)的DP解法就是这种思路的体现。贪心加二分的思路是维护一个当前最优的状态然后逐步更新它。这种思路的优点是效率高缺点是不太直观需要证明贪心策略的正确性。在LIS问题中O(n log n)的解法就是这种思路的体现。在实际比赛中如果时间允许我通常会先写一个O(n²)的DP解法确保逻辑正确然后再尝试优化成O(n log n)。这样既能保证正确性又能提升效率。如果时间紧张就直接写O(n log n)的解法但一定要仔细检查二分查找的边界条件。5.4 实际应用场景虽然“友好城市”是一道算法题但它背后的建模思路在实际中也有应用。比如在物流配送中我们需要把货物从多个仓库运送到多个目的地要求路线不交叉这就是一个类似的问题。再比如在电路板设计中我们需要把多个引脚连接起来要求连线不交叉这也是一个类似的问题。这些实际问题的共同特点是有两个维度的约束而且这两个维度之间存在单调性关系。一旦识别出这种结构就可以用排序加LIS的方法来求解。所以学好这道题不仅仅是为了应付比赛更是为了培养一种解决实际问题的建模能力。我在实际做题的时候发现很多看起来复杂的问题一旦找到了正确的建模方向就会变得非常简单。而找到正确方向的关键就是多做题、多总结、多思考。每做完一道题我都会问自己这道题的核心模型是什么这个模型还能解决哪些类似的问题这种反思习惯比单纯刷题的数量更重要。