企业官网建设流程全解析

如果你在某个高校OJ的题单里翻到过“Gym 101291A Alphabet”，会发现网上多数题解就甩一段LIS模板，然后把“最少删除”和“最长上升子序列”划上等号，中间怎么转化的、为什么是严格递增而不是按字典序不下降，基本没人细讲。这道题我从第一次AC到现在，见过三种不同问法的版本，每次都有新人栽在同一个地方。本文就把Alphabet题的完整建模思路、两种C++实现、隐蔽坑点和变式扩展一次说透，适合刚学完动态规划想拿LIS练手的同学，也适合想搞明白“删除字符类问题”该从哪下手的进阶选手。

题目本身不复杂：给你一个只含小写字母的字符串，每次可以删掉任意位置的任意个字符，问最少删多少次，才能让剩下的字符严格按字母表顺序排列。我第一次做也想过一堆贪心策略，折腾了快半小时，样例都过不全，后来意识到这题考的就是最长上升子序列，模型一转过来，十分钟就AC了。下面从题目拆解开始讲。

1. 拆题：Alphabet到底考的是什么

1.1 题目简史与输入输出

Gym 101291A 是某国际OJ的Gym题库里一道经典题，常被搬进各高校OJ作为动态规划入门训练题，标题里的SDUT字样一般就来自高校OJ的题单编号。题名Alphabet，直译是“字母表”，背景就是：给你一串字母，你想让它变成按字母表顺序排列的样子，问至少删掉多少个字母。

输入是一个只含小写字母的字符串，输出是一个整数。操作方式只有一种：删除字符，不能移动、不能替换、不能插入。这是关键，因为你唯一能改变的，就是“哪些字符留下”。

提示：有些OJ页面会把输入输出写成多组测试，所以代码里写成while (cin >> s)循环读取更稳，单组数据也能正常运行。

1.2 把题目翻译成人话

把题面翻译成更直白的逻辑：

• 最终留下来的字符，必须是原字符串的一个子序列，顺序不能变。
• 这个子序列必须严格递增，也就是每相邻两个字符，右边的字母一定比左边的大。
• 求这个子序列能达到的最大长度，然后用总长度减掉它，就是最少删除次数。

为什么是“子序列”而不是“子串”？因为删的是任意位置的字符，剩下的字符之间可能隔着被删掉的字符，只要前后相对顺序没变就行。子序列的定义正好就是“从原序列中挑出若干个元素，保持原有先后顺序”，所以删除操作和挑子序列是一一对应的。举例来说，对于字符串“aebc”，删掉e得到“abc”，“abc”在原串里不是连续的一段，但它是子序列，因为a、b、c的出现顺序与原串一致。子串要求连续，删除中间字符后剩下的通常都不是子串，所以这题跟子串没关系。

1.3 隐藏考点：一眼锁定LIS

到这里考点就很明显了：挑一个最长的、字符严格递增的子序列，这叫最长上升子序列，英文缩写LIS。所以答案等于字符串长度减去最长严格上升子序列长度。

这几乎是算法竞赛里最经典的DP模型之一，也是这道题唯一的正解方向。识别这个模型的能力比会写LIS模板更重要——很多题不会直接告诉你“求LIS”，而是包装成“删除字符”“堆塔”“排队找最长递增”之类的场景，核心都是同一个。识别方法就是找三要素：顺序固定、可挑选元素、最终要求单调性。三个条件同时出现，优先往LIS方向想，基本不会跑偏。

2. 删多删少的模型转化：从“删”到“留”

2.1 逆向思维：删最少等于留最长

新手最容易被“删除”带偏，因为删除是破坏性操作，直觉上会去想“删哪些”比较好，于是容易陷入贪心：从左到右扫，能留就留。这个思路第一眼是对的，实际上有反例，下面会专门说。

更干净的切入方式是反过来想：反正要删的是那些留不下的字符，那不如先决定“留下哪一串字符最划算”。留下来的条件就两条：在原串中按顺序出现，并且字母严格递增。于是问题就变成“最多能留下多少字符”，这个量就是LIS长度。

这个“破坏性操作转保留性操作”的思路，在很多字符串编辑题里都通用。比如求最少插入多少字符使字符串变为回文、求最少删除多少字符使两字符串相等，基本都是先转化成保留或匹配的最值问题。

2.2 严格递增：一个容易忽略的边界

先确认严格递增的含义。“abc”满足，因为a<b<c；“ace”也满足，因为a<c<e；“aab”不满足，因为第二个a并不大于第一个a。也就是说，同一个字母在结果里最多出现一次，因为两个相同字母不可能同时保留。

这个细节直接决定了用lower_bound还是upper_bound，也决定了DP的转移条件是s[j]<s[i]还是s[j]<=s[i]。如果只看中文题面“按字母表顺序排列”，非常容易误判成“不能逆序就行”，那“aab”就会被当成答案0，实际上是1。后面我会用完整例子复盘这个坑。

2.3 状态定义与递推关系

定义dp[i]表示：以原串第i个字符（下标从0开始）作为结尾的最长严格上升子序列长度。因为任何单字符本身就是一个长度为1的递增序列，所以dp[i]至少是1。

转移时，枚举所有在i前面的位置j，如果s[j] < s[i]，说明s[j]可以作为s[i]的前驱，那么dp[i]可以取dp[j]+1。取所有合法j里的最大值：

dp[i] = 1 + max(dp[j])，其中 j < i 且 s[j] < s[i]

最终LIS长度就是max(dp[i])。这个递推用两层循环实现，外层i从左到右，内层j从0到i-1，时间复杂度O(n²)。

用题名本身的单词“alphabet”来走一遍DP，很直观：

所以“alphabet”的LIS是4，答案是8-4=4。比如保留a、l、p、t这个递增序列，删除剩下四个字符，就能满足要求。

2.4 为什么贪心从左到右会错

有一个高频错误做法：维护当前保留的最后一个字符last，遍历原串，只要当前字符比last大就保留并更新last，否则丢弃。这本质是“能留就留”的局部贪心，并不能保证全局最优。

反例是字符串“aebc”：

• 贪心过程：保留a，遇到e保留，遇到b发现b<e丢弃，遇到c发现c<e丢弃，得到“ae”，长度2。
• 正确答案：保留a、b、c，得到“abc”，长度3，只需要删除1个字符。

问题在于，提前保留了一个较大的e，把后面所有较小的bc都挡住了。全局最优应该是“宁可暂时跳过大字符，也要为后面的小字符留机会”，这种选择不能靠单指针贪心完成，必须枚举所有子序列或使用DP。所以LIS不是“能续就续”，而是“每一段都要考虑以谁结尾最优”。

3. 两种主流解法：O(n²) DP 与 O(n log n) 贪心二分

3.1 写法一：O(n²)动态规划

O(n²)的DP是LIS的教科书写法，简单、不容易写错，也方便扩展出记录方案。核心就是前面那张表的代码化。完整代码：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; while (cin >> s) { int n = (int)s.size(); vector<int> dp(n, 0); int lis = 0; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (s[j] < s[i]) { dp[i] = max(dp[i], dp[j] + 1); } } lis = max(lis, dp[i]); } cout << n - lis << '\n'; } return 0; }

注意dp[i]初始化为1要放在内层循环之前，否则会被max操作污染初始值。lis的初始值设成0，这样即使输入为空串也能安全输出，虽然本题通常不会给空串。

这个写法的时间复杂度O(n²)。如果字符串长度在几千以内，完全没问题；如果数据被加强到10^5，就成了超时隐患，得用下面这种贪心二分写法。平时刷题可以顺便感受一下复杂度量级：n=100时一万次运算瞬间完成，n=10^5时百亿次运算基本跑不动，这就是为什么必须掌握更优写法。

3.2 写法二：O(n log n)贪心二分

第二种写法的核心是维护一个数组d：d[k]表示“长度为k+1的严格上升子序列中，结尾字符能达到的最小值”。遍历字符串的每个字符c，在d里找到第一个不小于c的位置，如果找不到，说明c比所有已知结尾都大，可以接到最长的递增序列后面，d长度加一；如果找到了，就用c替换那个位置的结尾。替换的意义是：同样长度的子序列，结尾字符越小，将来越容易接上更大的字符。

为什么要找“第一个不小于c”而不是“第一个大于c”？因为严格递增要求不能相等。假设d中已有'a'，现在又来了一个'a'，这两个'a'不能接在一起形成长度为2的严格递增序列，但可以用新的'a'替换旧的'a'作为长度为1的最小结尾——字母一样，替换后不影响正确性。而如果d里是比'a'大的字符，比如'd'，我们当然希望用'a'替换'd'，让长度为1的结尾更小。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; while (cin >> s) { vector<char> d; // 每个位置存的是长度为 idx+1 的最小结尾字符 for (char c : s) { auto it = lower_bound(d.begin(), d.end(), c); if (it == d.end()) { d.push_back(c); } else { *it = c; } } cout << (int)s.size() - (int)d.size() << '\n'; } return 0; }

时间复杂度O(n log n)，空间O(n)，是目前处理大范围数据的标准做法。两个写法答案完全一致，“alphabet”都会得到4。

提示：d里存的是字符，直接用char类型比较即可，'a'到'z'正好按ASCII码递增，不需要额外转数字。

3.3 两种写法怎么选

我的建议是：如果只是想快速AC且确认题目数据不大，用DP省心；如果数据范围未知或已知很大，就直接用二分写法。两种都写熟最好，因为很多LIS变体会要求你用其中一种改造。

4. C++实现细节：从能过样例到真正AC

4.1 输入输出的坑

题目输入是一个不含空格的字符串，用cin >> s读取即可，不要用getline。很多OJ版本会给出多组数据，所以while (cin >> s)是最安全的写法。如果题目明确只有一组，while写法也只会执行一次，没有副作用。

输出时注意类型：s.size()和d.size()返回的都是size_t无符号类型，直接相减虽然结果正确，因为d的长度不会超过s的长度，但为了干净，建议强转成int再相减。别小看这一步，有些编译器在开启严格警告时，无符号相减可能有隐蔽问题。

4.2 lower_bound的边界细节

用STL的话，lower_bound返回的是迭代器，判断it == d.end()表示c比d里所有字符都大，此时追加到末尾。否则直接赋值*it = c。vector的d会随着LIS长度动态增长，不需要预先开大数组，这也是比手写静态数组更不容易越界的原因。

如果非要手写二分，等价逻辑是：

int l = 0, r = (int)d.size(); // 查找第一个 >= c 的位置 while (l < r) { int mid = (l + r) / 2; if (d[mid] < c) l = mid + 1; else r = mid; } if (l == (int)d.size()) d.push_back(c); else d[l] = c;

这里有两个常见错误：一是循环条件写成l <= r，导致死循环；二是当d[mid] == c时走错分支。记住查找目标是“第一个不小于c的位置”，所以d[mid] < c时右移左边界，其余情况收缩右边界。手写二分的代码我看过太多人写反了，优先用STL的lower_bound更稳。

4.3 用三个样例验证答案

写完之后可以拿三组经典数据自测：

• 输入：abcdefghijklmnopqrstuvwxyz。整个字符串本身就是严格递增的，LIS=26，输出0，不需要删除。
• 输入：zyxwvutsrqponmlkjihgfedcba。完全降序，严格递增子序列最长只能取1个字符，LIS=1，输出25。
• 输入：alphabet。前面算过LIS=4，输出4。

如果这三组数据输出分别是0、25、4，说明核心逻辑基本正确，再去看边界和格式问题。自己造测试数据是竞赛里的基本功，别只依赖OJ给的样例。

4.4 关于数据范围的补充说明

这道题在常见的OJ版本里，字符串长度通常在几百以内，所以两种做法都能AC。如果以后在别的题单看到Gym 101291A的强化版，数据范围变成10^5，直接无脑用O(n log n)方案。判断数据范围是竞赛里的基本素养：拿到题先扫一眼n的量级再决定算法，别上来就套模板。

5. 踩坑复盘：三个隐蔽错误，我都被坑过

5.1 把“严格递增”写成“非递减”

这是Alphabet题最经典的坑。题目英文里强调的是alphabetical order，中文翻译容易变成“按字母表顺序排列”，于是把“aab”误判为已经有序。实际上按严格递增规则，“aab”的最长递增子序列是“ab”，长度2，答案是1。

如果你是按非递减去做，算法上的差异就是：DP转移把s[j]<s[i]写成s[j]<=s[i]；二分把lower_bound换成upper_bound。只差一个符号或一个函数，结果天差地别。

注意：拿到任何LIS变式题，第一件事就是确认“严格”还是“非严格”。题目说strictly increasing就是严格；说non-decreasing，或者样例里相等字符可以共存，就是非递减。Alphabet这个题名容易误导人，务必看样例、看英文原题。

5.2 二分查找的边界和方向

用STL不太容易错，但手写二分时，很多人把“找第一个>=c”和“找第一个>c”搞混，或者在d[mid]==c时不知道往哪边收缩。我的建议是直接背结论：

• 求严格递增LIS：用lower_bound(d.begin(), d.end(), c)。
• 求非递减LIS：用upper_bound(d.begin(), d.end(), c)。

如果笔试或竞赛要求手写，就用前面给的四行二分模板，不要现场现推边界。现场推细节是最容易出bug的环节，能背结论就背结论。

5.3 最后输出的是删除数，不是保留数

曾经有队友把这题AC代码交上去WA，查了半天发现是最后输出cout << lis而不是cout << n - lis。题目问“最少删除多少”，你算出来的是“最多留下多少”，两者差一个总长度。这种错误特别气人，因为样例可能恰好测不出来：如果样例串比较短，n-lis和lis的输出可能恰好相等。建议把输出那行单独拎出来写，并加一行注释“答案是删除数，不是LIS长度”。

6. 举一反三：Alphabet背后的题目家族

6.1 变式一：非递减版本

如果题目允许字符相等，比如“aab”本身合法，解法差异只在严格性上。DP写法把s[j] < s[i]改成s[j] <= s[i]；二分写法把lower_bound改成upper_bound。原因前面说过：非递减时，相等的字符可以接在后面形成更长的序列，所以查找替换位置时要跳过所有等于c的元素。

一个直观试金石：“aab”。严格递增版LIS=2，答案1；非递减版LIS=3，答案0。做这类题先拿“aab”当测试用例，能瞬间暴露你写的是哪个版本。

6.2 变式二：要求输出删除方案

如果题目从“求最少删除数量”升级成“输出删除哪些字符”，用O(n²)DP加pre数组最容易实现。具体来说：每次dp[i] = dp[j] + 1更新成功时，记录pre[i] = j；求完LIS后，从取得最大dp值的位置出发，沿着pre往前回溯，就能倒序恢复出保留的字符序列，剩下的就是被删除的字符。二分写法也能回溯，但需要额外维护pos数组记录每个d位置对应的原串下标，逻辑更绕，比赛里我一般不会用它输出方案。

6.3 变式三：字符集很小，用O(26n)的DP

这道题还有个容易被忽略的小技巧：字符集只有26个小写字母。既然字母种类这么少，可以不维护以位置结尾的dp，而是维护“以每个字母结尾的最长严格递增子序列长度”。

• 开一个best[26]数组，best[x]表示当前以字符x结尾的最长严格递增子序列长度。
• 遍历字符串每个字符ch，设x = ch - 'a'，枚举所有比x小的字母k（0到x-1），取其中最大的best[k]加1，用它更新best[x]。
• 因为严格递增，前驱只能来自字母严格小于x的序列，不能包含best[x]本身。
• 遍历完，max(best)就是LIS长度。

代码很短：

vector<int> best(26, 0); for (char ch : s) { int x = ch - 'a'; int mx = 0; for (int k = 0; k < x; k++) { mx = max(mx, best[k]); } best[x] = max(best[x], mx + 1); } int lis = *max_element(best.begin(), best.end()); cout << (int)s.size() - lis << '\n';

复杂度O(26n)，相当于O(n)，常数小，而且完全绕开了二分，很好理解。如果题目把严格递增改成非递减，只需把内层枚举改成k <= x。这个写法在字符集固定且很小的题里很实用，也能加深对LIS本质的理解——所谓“上升”，本质上就是在字母序上不断向后走。

6.4 更复杂的延伸：带权删除与区间化

如果每个字符删除的代价不一样，问题会变成最大权值递增子序列，可以用树状数组按字符值维护“以某字母结尾的最大权值和”，转移时查询前缀最大值。如果字符串变成二维网格或要求删除的是连续区间，模型会进一步复杂化。但无论怎么变，核心的“把删除转成保留，把保留定义成严格递增子序列”这个建模思路是不变的。先掌握基础LIS，再逐步加限制，就能应对大多数题目。

最后说点个人体会。我第一遍做这道Alphabet题的时候，其实卡在“为什么要用子序列而不用子串”上，后来把删除想成“选人参加比赛”就通了：你只能从候选人名单里按顺序挑人，挑出来的人必须一个比一个高。这个类比在我后来讲LIS时也特别好使。另一条经验是，凡是遇到字符串删除、保持顺序、最后要求某种单调性这三要素同时出现的题，优先往LIS方向想，基本不会跑偏。还有一个小技巧：调试时直接用“alphabet”这个单词当输入，答案4，串本身短、字母有重复、又贴合题名，比随机串好检查多了。如果你把这道题研究透了，“求最少删除使字符串有序”这一整类问题，以后就是送分题。