信息学奥赛一本通里那道编号 1286 的题题面挂着“怪盗基德的滑翔翼”这个名字很多刚学动态规划的同学第一眼是被名字吸引进去的结果读完题直接愣住——又是偷珠宝又是高楼滑翔到底要我算什么其实它在 OpenJudge NOI 2.6 章节里对应的是 4977两个编号同一道题都是线性 DP 里的入门模型。这篇就把这题从读题到 AC 的整个过程摊开讲包括状态怎么定义、为什么正反要跑两遍、等号加不加这些细节以及调试时怎么快速定位问题。不管你是刚接触信息学奥赛一本通的新手还是想回头梳理 DP 思路的老选手应该都能捞到点东西。1. 先把题意嚼碎基德到底能飞多远1.1 滑翔规则里的三个隐藏约束题目表面讲的是怪盗基德穿着一件能滑翔的披风在一排高楼之间穿梭。但真正决定解法的是藏在故事里的几个约束读题时如果漏掉任何一个代码思路就会直接跑偏。我把它拆成三条最关键的规则来理解。第一条滑翔只能“往下走”。滑翔翼没有动力只能从高处滑向低处所以后经过的建筑高度不能比当前更高。注意这里有个措辞问题是“严格更低”还是“不高于”多数版本的原题说的是“不高于”也就是允许高度相同等号要带上这一点后面专门讲。第二条起点是任意的。基德可以先站在任何一栋楼的楼顶起飞不需要从第一栋或者最高那栋出发。这意味着答案是所有可能起点里最优的那个而不是固定起点。第三条也是最多人卡住的地方滑翔方向只有左右两种而且选定方向后要一路走到底不能拐弯、不能来回。也就是说他要么从起点往左滑到尾要么从起点往右滑到尾二选一。这一点是理解整道题本质的钥匙很多同学一看到“高楼之间穿梭”就下意识以为可以随便跳结果写出了完全错误的解法。把这三条合起来翻译成人话就是在一排数里挑一个起点然后朝左或朝右找出一个高度不递增的序列问这个序列最长能有多长。1.2 为什么这题不是“贪心”而是“子序列”理解了上面三条规则就知道这题为什么不能靠贪心蒙过去。有同学会想从最高楼开始滑不就完了一路挑尽量高的下一栋这个思路听着顺但反例一抓一大把。比如高度是5 1 4 3 2如果贪心地从 5 开始挑“下一个不超过它且尽量大”的楼会先跳到 4然后跳 3再跳 2长度 4但如果从 5 开始老老实实跳到 1 就没了。而真正的最优解是从 4 往左到 1或者从 4 往右到 3 到 2长度 3。贪心在这里四处碰壁。核心原因是滑翔时被跳过的楼并不是“浪费”——它们可能属于另一个方向的更优路径或者属于另一个起点的最优解。我们没法只盯着局部最优做决定必须把所有起点、所有方向的可能性都纳入考虑。这正是“子序列”问题的典型特征序列里每个元素都有“选”或“不选”的自由最终要找的是一条满足单调约束的最长链。在信息学奥赛一本通和 OpenJudge 的动态规划章节里这类题被归为线性 DP因为它的状态是一维的、按位置递推的。认清它是子序列问题就自然知道该往“以第 i 个元素结尾的最长合法序列长度”这个方向去定状态而不是去写搜索或者贪心。这个判断过程本身就是一道经典训练题想教给你的东西。1.3 输入输出格式和一份手算样例这题的数据格式很朴素。第一行给测试数据组数每组第一行是建筑数量 n第二行是 n 个高度值一般是正整数可能相。输出每组一个整数表示该组数据下能滑过的最多建筑数。需要注意的是它是多组数据循环读入别只处理一组。我拿一组自造的数据把整条链路走一遍后面讲代码时也拿它对照输入 1 6 1 6 5 2 3 4高度序列是1 6 5 2 3 4。先看“向右滑”的情况从某栋楼往右找高度不递增的序列。比如从 6 出发能接 5再接 2 或 3 或 4都比 5 小但 2 后面比 2 小的没有3 后面 4 比 3 大也不行所以最长是6 5 2或6 5 3长度 3。再看“向左滑”从某栋楼往左找高度不递增换成正向看就是不下降。从最后一栋高度 4 往左看依次是 3、2、5、6、1能选的合法序列是从右往左递减也就是正向的1 2 3 4长度 4。所以这组数据的答案取两者最大值是 4路径就是高度1→2→3→4的那条从高度 4 的楼往左起飞依次经过高度 3、2、1 的楼。答案 4 就是我们后面所有代码要验证的目标值。手算这一步不能省它能帮你判断程序到底是哪里出了问题。2. 方案怎么选为什么DP才是正解2.1 暴力搜索会炸在哪里拿到题最直接的想法是搜索枚举每个起点、每个方向往下递归尝试每一种可能的降落选择。这个思路本身没错能出正确答案但复杂度扛不住。每个位置往后都有若干合法选择最坏情况下分支是指数级的n 稍微大一点就超时。具体地说如果在某次搜索里我们记录“从第 i 栋楼出发、方向确定时能走的最长距离”会发现同一个 (位置, 方向) 组合会被反复计算很多次。比如从位置 3 出发能走多长在起点是位置 1 的搜索里算过一遍在起点是位置 2 的搜索里又要重算。这种重叠子问题正是动态规划要用武之地。把所有重复计算缓存起来把指数级复杂度压到多项式级这就是这题从搜索走向 DP 的直接动机。所以正确的路径是先证明暴力是对的再找出暴力里重复计算的部分然后把它定义成状态、写出转移方程。这个过程我在带新人的时候一直强调DP 不是凭空变出来的公式而是压缩冗余计算的产物理解这一点比背方程重要得多。2.2 两个方向的独立建模因为基德只能朝一个方向一路走到底所以“向左”和“向右”是两条完全独立的路径可以分别求最后取最大值。这是这题最关键的简化。向右滑从某栋楼出发往右经过的高度不递增。如果我从右往左遍历数组定义L[i]表示“从第 i 栋楼向右出发能滑过的最多建筑数”那么L[i]就是“1 加上它右边所有不超过它的楼里L值的最大者”。为什么从右往左算因为算L[i]需要它右边所有位置的值已经算好从右往前推刚好满足这个依赖顺序。向左滑从某栋楼出发往左经过的高度不递增换成从左往右看就是高度不下降。定义R[i]表示“第 i 栋楼作为终点、从左边某处一路滑过来的最长链长度”也就是以i结尾的最长不下降子序列长度。这个从左往右算R[i]等于“1 加上它左边所有不超过它的楼里R值的最大者”。最终答案就是所有L[i]和所有R[i]里的最大值。两个方向各自独立、互不干扰这是能分开算的根本原因。2.3 正反各跑一遍的等价写法上面那种分L和R两个数组的写法最直观但还有一种更省心的等价写法很多老选手偏爱它把原数组和它的反转数组各跑一遍“最长不上升子序列”取最大值就行。为什么等价向右滑的原问题就是原数组的最长不上升子序列向左滑的原问题把数组反转之后就变成了反转数组的最长不上升子序列。两个问题被统一成了同一个函数代码能复用也更不容易写错。这里要提醒一句这里的“不上升”和“不下降”是同一件事的两种视角。原数组求最长不上升对应向右反转数组求最长不上升对应向左。搞混这两个视角是初学者最常见的翻车点后面第 4 章会专门拿它对账。用哪一种写法都行我个人在比赛里更倾向“正反各跑一遍”的版本因为核心函数只有一个调试时少一半变量要看。3. 代码落地从状态定义到手敲AC3.1 状态与转移方程的推导先把状态定义写清楚这是整段代码的地基。对向右滑我定义L[i]为从第 i 栋楼向右出发所能经过的最多建筑数初始L[i] 1因为最差情况就是只经过自己这一栋。转移方程是L[i] 1 max(L[j])其中 j 满足j i且h[j] h[i]。翻译一下要找第 i 栋楼右边所有“高度不超过它”的楼在这些楼里挑一个能走得最远的接在它后面。因为算L[i]依赖右边所以循环从 n 递减到 1。对向左滑定义R[i]为以第 i 栋楼结尾、从左边某处一路滑过来的最长链长度初始R[i] 1。转移方程是R[i] 1 max(R[j])其中 j 满足j i且h[j] h[i]。含义是找第 i 栋楼左边所有“高度不超过它”的楼在它们里挑能走最远的接上。算R[i]依赖左边循环从 1 递增到 n。推导时那个是怎么来的因为滑翔允许高度不高于当前楼所以“下一栋高度不超过当前”就写成h[j] h[i]。如果题目改成严格下降这里的等号就要去掉。两个方程的边界都是长度为 1 的自身。3.2 O(n^2) 完整实现与逐行讲解数据规模 n 不大双循环 O(n^2) 完全够用。下面这份代码我按“分两个数组”的写法给出逻辑最清晰#include iostream #include algorithm #include cstring using namespace std; int h[105]; int L[105]; // L[i]: 从 i 向右出发能滑过的最多建筑数 int R[105]; // R[i]: 以 i 结尾从左边滑过来的最长链 int main() { int T; cin T; while (T--) { int n; cin n; for (int i 1; i n; i) cin h[i]; int ans 0; // 方向一向右滑从右往左递推 for (int i n; i 1; i--) { L[i] 1; for (int j i 1; j n; j) { if (h[j] h[i]) { L[i] max(L[i], L[j] 1); } } ans max(ans, L[i]); } // 方向二向左滑等价于从左往右的最长不下降 for (int i 1; i n; i) { R[i] 1; for (int j 1; j i; j) { if (h[j] h[i]) { R[i] max(R[i], R[j] 1); } } ans max(ans, R[i]); } cout ans endl; } return 0; }逐行看几个容易忽略的点。L数组的循环是i从 n 到 1内层j从i1到 n这是为了确保算L[i]时右边所有值都算完了。R数组相反i从 1 到 n内层j从 1 到i-1保证左边先算。ans在两层循环里同步更新省得最后再遍历一次数组。拿第 1.3 节那组数据1 6 5 2 3 4跑一遍向右方向能得到最长 36 5 2向左方向能得到最长 41 2 3 4最后输出 4和手算一致。整份代码时间复杂度 O(n^2)空间 O(n)对 n100 的规模来说毫无压力。3.3 O(nlogn) 二分优化版如果哪天数据加强了n 涨到十万级别上面那份 O(n^2) 就会超时。这时候可以借用最长上升子序列的二分技巧把求“最长不上升子序列”的过程压到 O(nlogn)。思路是把求不上升转化成求不下降再用upper_bound维护一个辅助数组。具体做法是对于最长的非严格递减子序列可以把所有元素取相反数问题就变成求最长的非严格递增子序列。维护一个数组dd[k]表示当前长度为 k1 的合法子序列末尾元素的最小值。扫到某个值时用upper_bound找到它应该替换的位置。核心代码如下int lis_non_inc(int a[], int n) { int d[105], len 0; for (int i 0; i n; i) { int x a[i]; // 找 d 中第一个严格大于 x 的位置因为允许相等所以用 upper_bound int pos upper_bound(d, d len, x) - d; d[pos] x; if (pos len) len; } return len; }这里最容易搞错的就是用lower_bound还是upper_bound。结论是求非严格递增用upper_bound求严格递增用lower_bound。原因是允许相等时相等的元素可以接在同一长度上所以只替换“严格大于当前值”的位置。写反了结果会偏短。这题对 n 的要求不高二分版当作扩展了解即可但把这套upper_bound/lower_bound的对应关系吃透能顺带解决后面一大票子序列题。调用时对原数组跑一遍得到“向右”的最大值对反转后的数组再跑一遍得到“向左”的最大值两者取较大者逻辑和 O(n^2) 版完全一致。3.4 多组数据的处理细节这题是多组测试数据处理时有两个坑。第一数组一定要在每组数据开始时重新初始化。上面代码里L、R每个位置在循环里都先赋1相当于隐式重置能规避残留数据干扰但如果你用的是全局数组加memset记得别把 n 写错或者漏清。第二输出格式是每组一行别把答案攒到最后统一输出那样行数对不上直接判错。还有个小细节是读入方式。cin在本题数据量下足够快不需要scanf但如果养成了比赛习惯可以在main开头加一句ios::sync_with_stdio(false); cin.tie(0);遇到大数据量时不容易被卡输入。别小看这种习惯很多在线评测系统上 TLE 和 AC 的差距就是几百毫秒的输入优化拉开的。把这几条处理顺手了一份多组数据的题基本不会在格式上翻车。4. 踩坑实录那些年交上去的WA4.1 严格与非严格等号到底加不加这是这题排第一的翻车原因。判断条件是h[j] h[i]还是h[j] h[i]直接决定结果对不对。原题说的是滑翔翼“不高于”当前建筑也就是允许高度相同那么等号必须带。我见过太多人凭直觉写了严格小于样例勉强过了因为样例里往往没有相邻等高的楼一交上去就红。判断方法很简单自己在手算样例里插两个等高值试一下。比如把数据改成1 6 5 5 2 3 4如果允许相等从高度 5 的楼到另一个高度 5 的楼能接着走长度会比严格下降多一截。如果你代码的输出和手算对不上八成就是这里。顺带说一句很多同类题会明确写“严格下降”或“不高于”做题时把那个措辞圈出来条件照着措辞定别凭感觉。4.2 方向反了数组反转的两种姿势用“正反各跑一遍”的写法时最容易把方向弄反导致拿着一份 O(n^2) 的正确逻辑却输出错误答案。判断标准是原数组求“最长不上升”对应的是向右滑反转数组求“最长不上升”对应的是向左滑。你可以用一个单调递增的数组来验证比如1 2 3 4 5它向左滑的最优是5 4 3 2 1反向看是1 2 3 4 5长度 5而向右滑只有 1。跑一遍打印两个方向的结果哪个是 5 就对上了。反转数组有两种姿势一是用reverse(a1, an1)直接原地反转但要记得保留原数组的一份拷贝否则第二遍算的时候原始数据没了二是从 n 到 1 逆序读一遍写进新数组。我更推荐第二种清晰且不容易误改原数据。方向搞反这个问题本质是把“视角”和“实际方向”混为一谈多画一条箭头线在纸上比盯着代码硬想快得多。4.3 排查速查表与调试技巧实测下来这题的错误基本集中在几个固定位置。整理成一张速查表下次交之前对着过一遍现象最可能的原因快速修复样例能过但评测 WA等号方向写错漏了相等情况把改成试一次答案偏小两个方向漏算了一个检查L和R是否都更新了ans答案随机数组没清空上一组残留每组数据前重新初始化输出多一行/少一行多组数据格式问题每组独立输出一行二分版结果偏短用了lower_bound非严格场景改用upper_bound调试技巧上我强烈建议把两个方向的中间结果打印出来。比如打印L和R两个数组的完整内容肉眼对一遍哪个位置算错了比在 IDE 里单步快得多。尤其是第一遍写完没把握的时候先手算几组小数据长度 1、2、3 的极端情况再上大数据这样定位问题的范围会小很多。这道题总共几十行代码值得为它花十分钟做这种笨功夫。5. 举一反三这题背后的DP模型还能用在哪5.1 与合唱队形、导弹拦截的异同怪盗基德的滑翔翼本质是“单方向最长单调子序列”的组合。和它长得最像的是经典的“合唱队形”题那题要求先上升后下降用正反两遍最长上升子序列在同一个位置取和找峰值。滑翔翼和它的区别在于滑翔翼要么全程下降要么全程上升换视角不分段所以是独立取最大合唱队形是同一位置上升段加下降段拼起来是取和。这俩放在一起做能帮你彻底分清“单段最优”和“双段拼接”两种建模。再往外扩一点导弹拦截那道题里“最多拦截多少枚”其实就是最长不上升子序列和这题的向右滑完全同源“最少几套拦截系统”则是另一问Dilworth 定理那套属于进阶。把这几道题串起来做一遍你会发现线性 DP 里有一大类题都在求“满足某单调约束的最长子序列”状态定义和转移方程几乎是同一个模板换汤不换药。认准这个模板后面再遇到读起来花里胡哨的题也能一眼看穿它在考什么。5.2 搜索热词里的“弗洛伊德”是怎么回事顺便说个有意思的现象搜“信息学奥赛一本通”的时候热词里经常混进“弗洛伊德算法”。很多人一看这个词和滑翔翼摆在一起还以为这题要用最短路或者传递闭包直接跑偏去找图论那套东西了。这里明确一下弗洛伊德算法是求所有点对最短路的属于图论、递推型的三重循环和这题的序列 DP 没有半点关系。它们唯一的共同点是都写在信息学奥赛一本通这套书里被搜索引擎的标签系统凑到了一块。我提这个是想说明一件事搜题的时候要认准题目本身的关键词别被旁边冒出来的热词带节奏。热词是给检索用的不是给解题用的。做题时以教材上的题号和题面为准网上各种“XX题库答案”仅供参考真要理解思路还是得自己把样例动手跑一遍。这也是我一直建议新手别只对着答案抄的原因抄得来的只有代码抄不来的是建模的直觉。5.3 数据加强后该怎么办原题 n 在百级别O(n^2) 足够。但如果数据加强到十万级就得换 O(nlogn) 的二分版思路在第 3.3 节已经给过了。再往上如果允许基德在空中“拐一次弯”比如先向左滑一段再向右滑一段问题就变成合唱队形那种峰值模型需要在同一位置合并两个方向的结果不再简单取最大值。这类变形在提高组里很常见考的就是你能不能识别出“单段”和“多段拼接”的差别。最后一个实际建议把这道题的代码封装成一个函数输入一个数组返回最长滑翔长度这样以后遇到同类题能直接复用。我在做专题训练时就是这么干的把“最长不上升”“最长不下降”“先升后降”几个函数各写成模板存起来比赛里遇到相关题直接调用省下的是最宝贵的编码时间。模板这种东西平时攒得越勤关键时刻越不慌。