1. 项目背景与问题拆解从“游园安排”到最长上升子序列看到“游园安排”这个标题很多参加过算法竞赛的朋友可能会心一笑。这其实是蓝桥杯2020年国赛的一道经典题目它表面上是一个关于游园路线规划的故事但内核却是一个经典的动态规划问题——最长上升子序列Longest Increasing Subsequence, LIS。题目通常会给你一个字符串序列代表游客的姓名或某种标识你需要从中找出一个最长的、按字典序严格递增的子序列。这里的“递增”不是数值大小而是字符串在字典序上的先后关系。为什么这道题值得拿出来单独讲因为在算法竞赛和面试中LIS问题及其变种出现的频率极高。它不仅是动态规划的入门必修课更是检验选手是否真正理解状态定义与转移的“试金石”。很多初学者能背出O(n²)的模板但一旦遇到像“游园安排”这样需要输出具体方案、且元素是字符串的变种就很容易卡壳。更不用说在数据量大的情况下如何将复杂度优化到O(n log n)并同时记录路径这其中的技巧和细节正是区分普通选手和高手的关键。我自己在准备比赛和后来带学生刷题的过程中发现大家在这类问题上的主要困惑点有几个第一如何将抽象的“安排”问题准确建模成LIS第二在优化到O(n log n)的贪心二分算法中如何记录下最终的子序列而不仅仅是长度第三当存在多个合法的最长序列时如何按题目要求输出字典序最小的那个。接下来我就结合“游园安排”这道题把LIS问题的“里子”和“面子”都掰开揉碎了讲清楚让你不仅会做这一道题更能掌握解决一大类问题的思路。2. 问题建模如何将游园名单转化为LIS模型首先我们得把题目描述“翻译”成算法语言。假设题目输入是一个字符串数组names例如[Wo, Aken, Mike, Anna, Bob]。我们需要找到一个最长的子序列使得这个子序列中的字符串严格按照字典序递增排列。注意是子序列不是子串。这意味着我们可以跳过中间的一些人只要保留下来的顺序是原顺序且字典序递增即可。例如对于上面的数组一个合法的递增子序列是[Aken, Bob]但更长的可能是[Aken, Anna, Bob]吗不对因为 “Anna” 和 “Bob” 在原数组中的顺序是Anna在Bob之前但字典序上Anna Bob是成立的所以[Aken, Anna, Bob]是一个长度为3的合法子序列。我们需要找到的就是最长的那个。这直接对应了最长上升子序列LIS的定义在一个序列中找到一个最长的子序列使得这个子序列的元素单调递增。只不过在经典LIS中元素通常是数字比较规则是数值大小而在这里元素是字符串比较规则是字典序。字符串的字典序比较在编程语言中如C的string Java的String.compareTo Python的是直接支持的因此模型转换非常直接。所以问题的核心模型就是给定一个序列字符串数组求其字典序意义下的最长上升子序列的长度并且需要输出这个子序列本身。当有多个方案时输出字典序最小的方案。这里“字典序最小”指的是在所有可能的最长上升子序列中将它们视为一个字符串序列从头开始比较第一个出现不同字符的位置字符较小的那个序列被视为更小。这个要求增加了问题的复杂度因为我们需要在记录方案时进行额外的比较和选择。3. 算法核心从O(n²)动态规划到方案记录我们先从最直观的动态规划解法开始这是理解问题本质的基础。定义dp[i]表示以第i个字符串names[i]作为结尾的最长上升子序列的长度。状态转移方程很容易想到dp[i] max(dp[j]) 1其中0 j i且names[j] names[i]字典序小于。 也就是说对于每个位置i我们看看它前面有哪些位置j的字符串比它小然后从那些位置中选一个dp[j]值最大的接在后面就形成了以i结尾的更长的子序列。这个算法的时间复杂度是 O(n²)对于n在 10^3 数量级的数据是可行的。但蓝桥杯的国赛题数据规模往往会卡这个复杂度要求我们使用 O(n log n) 的优化算法。不过O(n²) 的DP有一个巨大的优点非常容易记录具体方案。我们只需要在更新dp[i]的同时用一个pre[i]数组记录下是从哪个j转移过来的即names[i]的前驱节点。最后我们找到dp值最大的位置pos然后通过pre数组向前回溯就能还原出整个子序列。这里就遇到了第一个关键细节当有多个j都能使dp[i]达到最大值时我们选择哪一个作为前驱这直接影响了最终回溯得到的序列的字典序。题目要求输出字典序最小的最长子序列。一个常见的错误思路是在转移时如果dp[j] 1 dp[i]并且names[j]的字典序比当前记录的前驱pre[i]对应的字符串更小就更新pre[i] j。然而这个策略是错误的。为什么因为字典序的比较是全局的、逐位比较的。仅仅让每个位置i选择它前面字典序最小的前驱并不能保证最终整个序列的字典序最小。考虑这个例子序列[“b”, “a”, “c”]。最长上升子序列长度是2有两个[“b”, “c”]和[“a”, “c”]。字典序最小的是[“a”, “c”]。如果按照上述“局部最小”策略对于“c”它的前驱可以是“b”或“a”两者dp值都是1。因为“a”字典序小于“b”所以pre[“c”]会选择“a”。这看起来是对的。但如果我们把序列加长[“b”, “a”, “d”, “c”]。最长上升子序列长度还是2有多个。现在对于“d”它的前驱“b”和“a”的dp值都是1它会选择“a”。对于“c”它前面比它小的有“b”,“a”“d”“d”比“c”大不考虑。“b”和“a”的dp值都是1“c”也会选择“a”作为前驱。那么以“c”结尾的序列就是[“a”, “c”]。但这是全局最小的吗不一定因为以“d”结尾的序列[“a”, “d”]字典序可能比[“a”, “c”]更小“c”和“d”比较。实际上我们需要在所有dp值最大的位置中比较以它们结尾的整个序列的字典序。因此在 O(n²) DP 中一个可靠的做法是先完整计算出所有dp[i]和pre[i]当多个j的dp[j]相同时可以任意选一个比如第一个遇到的j因为后续我们会统一比较。然后我们找到所有dp值等于最大长度maxLen的位置这些位置是潜在的终点。对于每一个这样的终点我们通过pre链回溯构造出完整的序列。最后在所有构造出的序列中选择字典序最小的那个输出。这个方法逻辑清晰但构造和比较序列的过程在 n 较大时会比较耗时不过对于 O(n²) 算法而言这通常仍在可接受范围内。注意在回溯构造序列时由于我们是从终点倒推到起点得到的序列是逆序的需要反转一下才能得到正序。4. 优化算法O(n log n)的贪心二分与路径记录O(n²) 的算法在 n 超过 10^4 时就力不从心了。标准的 LIS 优化算法是贪心二分可以将时间复杂度降至 O(n log n)。这个算法的核心思想是维护一个数组dd[len]表示长度为len的上升子序列的末尾元素的最小可能值。注意d本身并不是一个合法的 LIS但它能帮助我们快速计算最大长度。算法流程如下初始化d为空长度len 0。遍历原序列的每个元素names[i] a. 如果names[i]大于d的最后一个元素即大于所有长度为len的序列的末尾那么它可以接在后面形成更长的序列。d[len] names[i]。 b. 否则在d数组中找到第一个大于等于names[i]的位置pos并用names[i]替换掉d[pos]。这个查找过程用二分法完成。这个算法妙就妙在它通过维护“末尾最小”这个贪心策略保证了d数组是单调递增的这允许我们使用二分查找并且d的长度len就是最终 LIS 的长度。但它有一个“致命”的缺点d数组最终存储的并不是一个真实的 LIS我们无法直接从d数组回溯出原序列。例如序列[2, 5, 3, 4]d数组的最终状态是[2, 3, 4]长度是3但d本身[2,3,4]在原序列中的下标顺序并不是递增的3在5后面。那么如何在 O(n log n) 的算法中记录路径呢这就需要我们引入另一个辅助数组pos。具体做法是我们不仅维护d数组还维护一个等长的pos数组。pos[len]记录的是当d[len]被更新为某个值时这个值在原序列中的下标i。同时我们还需要一个pre数组长度等于原序列 npre[i]记录的是在以names[i]结尾的当前最优子序列中names[i]的前一个元素在原序列中的下标。更新逻辑如下遍历到names[i]。在d数组中进行二分查找找到第一个大于等于names[i]的位置p。更新d[p] names[i]同时更新pos[p] i。这表示长度为p的子序列其末尾最小元素更新为names[i]且这个元素在原序列的位置是i。关键一步记录前驱。names[i]的前驱就是构成长度为p-1的子序列的末尾元素。这个末尾元素的下标记录在pos[p-1]里。所以我们令pre[i] pos[p-1]。注意当p 1时表示这是长度为1的子序列没有前驱我们可以设pre[i] -1。通过这种方式我们为原序列中的每个元素i都记录了它在“当前已知的、以它结尾的最长上升子序列”中的前驱。当算法结束后d的长度len就是 LIS 的长度。LIS 的最后一个元素的下标就是pos[len]。然后我们就可以通过pre数组从这个下标开始不断向前回溯直到-1从而得到整个 LIS 在原序列中的下标路径进而得到字符串序列。5. 处理字典序最小比较策略的终极技巧现在我们有了在 O(n log n) 时间内记录路径的方法。但是这记录的是“某一条”最长上升子序列的路径。当存在多条时我们如何确保得到的是字典序最小的那一条呢回顾一下d数组的定义d[len]存储的是长度为 len 的上升子序列的末尾元素的最小可能值。这个“最小可能值”的贪心策略本身就倾向于让序列的末尾尽可能小。但这对于保证整个序列的字典序最小是充分条件吗并不是。d数组保证的是对于每一个固定的长度其末尾元素是可能达到的最小值。但这并不能直接推导出由这些“最小末尾”连接起来的序列其整体的字典序就是最小的。因为字典序是从头开始比较的前面的字符权重更大。这里就需要一个非常重要的洞察为了得到字典序最小的最长上升子序列我们应该从后往前构造它。或者说在回溯的时候如果我们有多个选择我们应该选择能使前面部分字典序更小的那个选择。具体到我们的算法中当我们在d数组中用二分查找找到位置p时我们执行的是d[p] names[i]。如果有多个names[i]可以放在d[p]这个位置即它们都等于当前的d[p]按照标准的贪心算法我们不会更新d[p]因为值没有变小。但是为了得到字典序更小的最终序列当names[i]等于当前的d[p]时我们也应该更新它同时更新pos[p] i和pre[i] pos[p-1]。为什么考虑两个值相等的字符串它们字典序相同。但是它们在原序列中处于不同的位置。选择位置更靠后的那个作为d[p]可能会为更长的子序列p1, p2, ...提供更多、更“小”的选择从而可能影响到最终序列前面部分的选择。然而这个策略需要仔细分析。实际上一个更稳妥、更通用的方法是我们不在更新d数组时做特殊处理而是在最后回溯构造序列时进行精细的比较和选择。算法结束后我们知道了最大长度len。LIS 的最后一个元素的下标是pos[len]。但pos[len]只记录了最后一个被更新到d[len]位置的那个元素的下标。如果历史上有多個元素都曾作为d[len]即它们都曾作为某个长度为len的子序列的末尾那么pos[len]只保存了最后一个。我们需要的是所有可能作为结尾的下标。因此我们需要改进记录方式。我们不再只用一个pos数组而是用一个vector数组endsAt[len]来记录所有能够形成长度为len的上升子序列的末尾元素的下标。在更新时如果names[i]大于d[len]那么它可以形成长度为len1的序列。d[len] names[i]并将i加入到endsAt[len]中。pre[i]可以从endsAt[len-1]中任意一个下标转移过来通常我们选最后一个因为后续会比较。如果names[i]需要替换d[p]那么d[p] names[i]并且将i加入到endsAt[p]中。同样pre[i]从endsAt[p-1]中获取。最终我们得到endsAt[len]里面是所有可能作为最长子序列末尾的下标。我们的目标是从endsAt[len]中选一个下标开始回溯使得回溯得到的整个序列的字典序最小。如何比较暴力方法是对endsAt[len]中的每个下标都回溯出一个序列然后比较这些序列的字典序。但这样最坏情况是 O(n²) 的。我们可以用动态规划的思想从后往前递推每个位置的“最佳后继”。定义bestFrom[i]表示从下标i开始即以names[i]作为序列的第一个元素能够构成的最长上升子序列是什么用字符串序列表示。但这个状态空间太大。一个巧妙的做法是我们知道了最大长度len那么对于长度为k的子序列我们总是希望它的第一个元素尽可能小因为字典序是从头比较的。因此我们可以从k len递减到k 1来构造序列设currentLen len。在endsAt[currentLen]中选择对应字符串字典序最小的那个下标i作为我们序列中第currentLen个元素从后往前看是第一个。然后我们需要找到第currentLen-1个元素。它应该在endsAt[currentLen-1]中并且满足两个条件a) 它的下标j必须小于我们刚选的i因为子序列要保序b)names[j] names[i]因为要严格递增。在满足条件的j中我们再次选择names[j]字典序最小的那个。重复步骤3-4直到currentLen变为0。这个算法在每一步都选择当前条件下字典序最小的元素从而保证了最终序列的字典序最小。实现时我们可以对每个endsAt[k]按下标排序然后用二分查找快速找到满足j i且names[j] names[i]的候选者中字典序最小的那个。由于k从len递减到1且每个endsAt[k]的大小总和是 O(n) 的整体复杂度可以控制在 O(n log n)。6. 代码实现与细节剖析理论讲完了我们来看具体代码实现。这里我用 C 给出一个清晰且带有详细注释的版本它实现了 O(n log n) 的贪心二分算法并妥善处理了路径记录和字典序最小的问题。选择 C 是因为其在算法竞赛中的高效和普遍性但思路完全适用于其他语言。#include iostream #include vector #include string #include algorithm using namespace std; int main() { string s; cin s; // 假设输入是一个长字符串名字之间没有空格需要分割 // 题目通常名字是连续大写字母开头我们可以根据大写字母来分割 // 这里简化处理假设输入已经是空格分隔的名字字符串或者我们手动分割。 // 例如输入 Wo Aken Mike Anna Bob vectorstring names; // 分割字符串的代码根据具体输入格式调整 // 这里假设用空格分割 size_t pos 0; while ((pos s.find( )) ! string::npos) { names.push_back(s.substr(0, pos)); s.erase(0, pos 1); } if (!s.empty()) names.push_back(s); int n names.size(); if (n 0) { cout endl; return 0; } // d[len] 表示长度为len的LIS的末尾字符串的最小值 vectorstring d(n 1); // pos[len] 记录d[len]对应的原序列下标这里我们只记录最后一个简化版 // 为了处理字典序最小我们需要更复杂的记录这里先给出简化版可能得不到字典序最小 vectorint pos(n 1, -1); // pre[i] 记录以names[i]结尾的LIS中前一个元素的下标 vectorint pre(n, -1); int len 0; // 当前已知的LIS最大长度 for (int i 0; i n; i) { // 二分查找第一个 names[i] 的位置 int l 1, r len, p len 1; // p初始化为len1表示需要扩展 while (l r) { int mid (l r) / 2; if (d[mid] names[i]) { // 注意这里是 为了替换第一个的 p mid; r mid - 1; } else { l mid 1; } } // 更新d和pos d[p] names[i]; pos[p] i; // 记录前驱 if (p 1) { pre[i] pos[p - 1]; } else { pre[i] -1; } if (p len) { len p; } } // 此时len就是最大长度 // 但上面的简化版pos只记录了最后一个要得到字典序最小需要从所有可能的结尾中选 // 我们需要找到所有dp值等于len的i这里dp[i]可以通过另一种方式记录或者重构 // 重构dp值我们可以再跑一遍或者利用pre和len倒推。 // 更健壮的方法是维护一个dp数组dp[i]表示以i结尾的LIS长度 // 我们在二分查找时p就是以names[i]结尾的LIS长度 vectorint dp(n); // 重新初始化d和pos同时记录dp d.assign(n 1, ); len 0; for (int i 0; i n; i) { int l 1, r len, p 1; while (l r) { int mid (l r) / 2; if (d[mid] names[i]) { r mid - 1; } else { p mid 1; l mid 1; } } // 另一种二分写法找到第一个的或者最后一个的1 // 这里我们采用另一种常见写法 p lower_bound(d.begin() 1, d.begin() len 1, names[i]) - d.begin(); d[p] names[i]; dp[i] p; if (p len) len p; } // 现在dp[i]存储了以i结尾的LIS长度 // 找出所有dp[i] len的i vectorint candidates; for (int i 0; i n; i) { if (dp[i] len) { candidates.push_back(i); } } // 从candidates中构造序列并选择字典序最小的 // 由于要字典序最小我们需要从后往前构造并每次选择当前合法的、字典序最小的字符串 vectorstring ans(len); int currentIndex -1; int currentLen len; // 从最后一位开始选 for (int k len; k 1; --k) { // 在所有dp[i] k 的i中选择names[i]字典序最小的并且要满足 // 如果已经选了后面的元素currentIndex则这个i必须 currentIndex 且 names[i] names[currentIndex] string minStr {; // ASCII中{比所有字母都大用作初始最大值 int chosen -1; for (int i : candidates) { if (dp[i] ! k) continue; if (currentIndex ! -1) { if (i currentIndex || names[i] names[currentIndex]) continue; } if (names[i] minStr) { minStr names[i]; chosen i; } } // 找到当前位的最佳选择 ans[k - 1] minStr; currentIndex chosen; // 下一轮候选者范围可以缩小为所有下标小于chosen且dp值为k-1的 // 这里我们简单地将candidates更新为所有满足条件的i实际可以优化 vectorint newCandidates; for (int i 0; i n; i) { if (dp[i] k - 1 i currentIndex names[i] names[currentIndex]) { newCandidates.push_back(i); } } candidates std::move(newCandidates); } // 输出结果 for (int i 0; i len; i) { cout ans[i]; if (i ! len - 1) cout ; } cout endl; return 0; }这段代码是一个相对清晰的实现但其中关于字典序最小的处理部分最后那个循环在极端情况下可能不是最优的但清晰地展示了思路。在实际竞赛中为了效率我们通常会采用更精巧的数据结构如根据dp值和下标构建二维结构并排序来加速查找过程。但核心思想不变从后往前在满足递增关系和顺序关系的约束下每一步都贪心地选择字典序最小的字符串。7. 常见踩坑点与调试心得即使理解了算法实现时也难免踩坑。这里分享几个我在这道题以及类似LIS问题中总结的常见陷阱1. 二分查找的边界与条件这是最容易出错的地方。在贪心二分算法中我们是要找第一个大于等于names[i]的位置对于严格递增LIS。如果写成找第一个大于的位置对于连续相等的字符串算法可能就无法正确更新导致长度计算错误。lower_bound函数就是干这个的。如果自己手写二分务必注意循环条件和更新逻辑。一个简单的测试输入序列[“a”, “a”, “a”]最长严格递增子序列长度应该是1。如果你的算法输出3那肯定是比较条件写错了应该是而不是。2. 字典序比较与字符串相等题目要求“严格递增”这意味着names[i]必须小于names[j]不能等于。在比较时直接使用运算符即可。但要注意在记录路径选择前驱时如果遇到字典序相等的字符串它们不能接在彼此后面因为不满足严格递增但它们可以作为不同位置的候选。在最后构造字典序最小序列时相等字符串的选择会影响结果因为它们在原序列中的位置不同。3. 路径回溯时的下标与值混淆pre[i]记录的是前驱的下标不是字符串本身。在回溯时我们是从一个下标i通过pre[i]跳到上一个下标j。最终得到的是一串下标需要再映射回names数组才能得到字符串序列。务必保持清醒不要混用。4. 多方案字典序最小的处理时机正如前面所讨论的在 O(n log n) 算法中简单地用pre数组记录前驱最后从pos[len]回溯得到的可能不是字典序最小的。必须在得到所有可能的终点dp[i]len的 i后进行全局的比较和选择。一个常见的简化方法是在更新d[p]时如果names[i]等于当前的d[p]我们也进行更新即用i替换pos[p]。这个策略基于一个假设对于相同的末尾值选择更靠后的位置可能在构造更前面的部分时有更多选择从而可能得到字典序更小的序列。这个假设在大多数情况下是成立的并且能通过蓝桥杯的评测数据但它并不是严格正确的。不过对于竞赛而言这是一个行之有效的“启发式策略”可以简化代码。如果追求绝对正确就需要实现前面提到的从后往前贪心选择的完整逻辑。5. 输入格式的解析“游园安排”题目的输入往往是一个长字符串所有名字连在一起每个名字以大写字母开头。例如WoAkenMikeAnnaBob。你需要正确地分割出每个名字。分割逻辑要写对遍历字符串遇到大写字母就开始一个新的名字直到下一个大写字母之前。这是基础的字符串处理但写错了会导致整个结果错误。建议单独写一个分割函数并打印分割后的结果进行验证。调试时最好先用小规模、有代表性的数据测试。例如测试严格递增序列[“A”, “B”, “C”, “D”]结果应为本身。测试严格递减序列[“D”, “C”, “B”, “A”]结果应为任意一个字符长度为1。测试有相等元素的序列[“A”, “A”, “B”, “B”]最长严格递增子序列应为[“A”, “B”]长度为2。测试字典序最小的选择[“B”, “A”, “C”]最长长度为2有两个序列[“B”, “C”]和[“A”, “C”]你的程序应输出[“A”, “C”]。测试更复杂的序列[“Wo”, “Aken”, “Mike”, “Anna”, “Bob”]手动推导一下正确结果然后和程序输出对比。8. 举一反三LIS变种问题与扩展思考掌握了“游园安排”这道题你基本上就掌握了LIS问题的核心。但算法竞赛的魅力就在于变化。这里列举几个常见的LIS变种你可以用我们上面讨论的思路去尝试解决1. 最长不下降子序列Longest Non-decreasing Subsequence这是将“严格递增”改为“非严格递增”即允许相等。在贪心二分算法中只需要将二分查找的条件从“第一个大于等于”改为“第一个大于”即可。因为对于d数组我们现在希望它维护的是“长度为 len 的不下降子序列的末尾元素的最小可能值”。当遇到一个等于当前末尾的元素时它可以接在后面而不破坏“不下降”的性质所以我们应该去更新第一个大于它的位置而不是大于等于。2. 二维偏序问题如信封嵌套、俄罗斯套娃这类问题通常给出一组二元组(w, h)要求找到一个序列使得w和h都严格递增或满足某种偏序关系。一个经典的解法是先对其中一个维度如w进行排序然后在另一个维度h上找 LIS。但需要注意当w相等时为了避免误选通常需要对h进行降序排序然后再在h上找 LIS。这就将二维问题转化成了一维 LIS。3. 输出所有最长上升子序列的个数这需要结合动态规划计数。在 O(n²) 的DP中可以定义cnt[i]为以i结尾的最长上升子序列的个数。在转移时如果dp[j] 1 dp[i]则更新dp[i]并重置cnt[i] cnt[j]如果dp[j] 1 dp[i]则cnt[i] cnt[j]。最后将所有dp[i] maxLen的cnt[i]累加。在 O(n log n) 的算法中计数会变得复杂需要维护d数组每个位置对应的方案数涉及到去重是一道不错的进阶练习题。4. 带权值的LIS最大上升子序列和每个元素有一个权值求权值和最大的上升子序列。此时dp[i]的定义可以变为以i结尾的最大权值和。状态转移方程类似dp[i] max(dp[j]) weight[i]其中j i且val[j] val[i]。这通常只能用 O(n²) 的DP求解。如果数据范围大可以考虑用数据结构如树状数组、线段树来优化前缀最大值查询将复杂度降至 O(n log n)。回到“游园安排”它之所以经典是因为它融合了 LIS 的长度求解、路径记录和多方案择优这三个核心难点。通过这道题你应该建立起这样的思维模式遇到序列上的最优子序列问题先考虑是不是 LIS 的变种如果需要输出方案思考如何在状态转移时记录前驱如果方案不唯一且有择优要求分析择优的标准是全局的还是局部的并设计相应的比较和选择策略。最后再强调一个工程实践中的技巧在竞赛中如果时间紧迫对于“输出字典序最小方案”这类要求如果想不到完美的 O(n log n) 解法完全可以先实现一个正确但稍慢的 O(n²) DP 来求具体方案。在 n 不超过 5000 时O(n²) 是完全可行的。先把分数拿到再去思考优化。毕竟正确的算法比高效的错误算法要好得多。