NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 25 题

#include <stdio.h> 
const int SIZE = 100; 
int main()  
{ 
 int height[SIZE], num[SIZE], n, ans; 
 int i, j; 
 scanf("%d", &n); 
 for (i = 0; i < n; i++) { 
  scanf("%d", &height[i]); 
  num[i] = 1; 
  for (j = 0; j < i; j++) { 
   if ((height[j] < height[i]) && (num[j] >= num[i]))  
    num[i] = num[j]+1; 
  } 
 } 
 ans = 0; 
 for (i = 0; i < n; i++) { 
  if (num[i] > ans) ans = num[i]; 
 } 
 printf("%d\n", ans); 
 return 0; 
} 

输入： 8 3 2 5 11 12 7 4 10 输出：_________

这题就是考最长上升子序列（LIS），别被数组名 num 和 height 绕晕了，直接按代码逻辑一步步模拟：外层 i 从 0 扫到 n-1，内层 j 从 0 扫到 i-1，只要 height[j] < height[i] 且 num[j] >= num[i]，就把 num[i] 更新成 num[j]+1。最后取所有 num[i] 的最大值就是答案。

很多学生看到 LIS 就下意识想 O(n log n) 的二分写法，或者以为必须连续才算子序列（其实不要求连续，只要相对顺序不变），这两个坑最容易掉进去。另外，代码里那个 if 条件 (height[j] < height[i]) && (num[j] >= num[i]) 是动态规划的状态转移核心，如果只盯着 height 的大小比较，忘了 num 的更新逻辑，就会算错每个位置结尾的 LIS 长度。还有，最后求的是所有 num[i] 的最大值，别只盯着最后一个 num[n-1]，万一后面某个数虽然比前面大但它的 LIS 长度反而小，最大值可能出现在中间某个位置。

这道题考查的是经典的最长上升子序列（LIS）问题，属于动态规划的基础题型。命题人喜欢用这种看似复杂的嵌套循环来包装一个简单算法，考察学生是否能透过代码表象理解状态转移的本质。LIS 的核心概念是：在一个序列中找出一个子序列（不要求连续），使得子序列中的元素严格递增，并且长度最长。本题给出的序列是 3 2 5 11 12 7 4 10，我们需要求它的 LIS 长度。

程序采用了 O(n²) 的动态规划解法。它定义 num[i] 表示以第 i 个元素结尾的最长上升子序列的长度。初始化时，每个位置至少能构成一个只含自身的子序列，所以 num[i] 初始化为 1。然后，对于每个位置 i，程序向前扫描所有 j < i 的位置，如果发现 height[j] < height[i]（说明可以接在 j 后面）且 num[j] >= num[i]（说明接在 j 后面能让 i 的 LIS 长度变长），就把 num[i] 更新为 num[j] + 1。这个 if 条件其实就是状态转移方程：num[i] = max(num[i], num[j] + 1)，其中 j 遍历所有满足 height[j] < height[i] 的前驱。最后，ans 取所有 num[i] 的最大值，就是整个序列的 LIS 长度。

现在我们来逐行模拟执行过程。输入 n=8，序列为 3 2 5 11 12 7 4 10。

i=0，height[0]=3：num[0] 初始为 1，内层 j 没有元素，num[0] 保持 1。 i=1，height[1]=2：num[1] 初始为 1，j=0 时 height[0]=3 不小于 2，条件不满足，num[1] 保持 1。 i=2，height[2]=5：num[2] 初始为 1，j=0 时 height[0]=3 < 5 且 num[0]=1 >= 1，num[2] 更新为 2；j=1 时 height[1]=2 < 5 且 num[1]=1 >= 2 不成立，num[2] 保持 2。 i=3，height[3]=11：num[3] 初始为 1，j=0 时 3<11 且 1>=1，num[3] 变为 2；j=1 时 2<11 且 1>=2 不成立；j=2 时 5<11 且 2>=2 成立，num[3] 变为 3；num[3] 最终为 3。 i=4，height[4]=12：num[4] 初始为 1，j=0 时 3<12 且 1>=1，num[4] 变为 2；j=1 时 2<12 且 1>=2 不成立；j=2 时 5<12 且 2>=2 成立，num[4] 变为 3；j=3 时 11<12 且 3>=3 成立，num[4] 变为 4；num[4] 最终为 4。 i=5，height[5]=7：num[5] 初始为 1，j=0 时 3<7 且 1>=1，num[5] 变为 2；j=1 时 2<7 且 1>=2 不成立；j=2 时 5<7 且 2>=2 成立，num[5] 变为 3；j=3 时 11 不小于 7，跳过；j=4 时 12 不小于 7，跳过；num[5] 最终为 3。 i=6，height[6]=4：num[6] 初始为 1，j=0 时 3<4 且 1>=1，num[6] 变为 2；j=1 时 2<4 且 1>=2 不成立；j=2 时 5 不小于 4，跳过；j=3 时 11 不小于 4，跳过；j=4 时 12 不小于 4，跳过；j=5 时 7 不小于 4，跳过；num[6] 最终为 2。 i=7，height[7]=10：num[7] 初始为 1，j=0 时 3<10 且 1>=1，num[7] 变为 2；j=1 时 2<10 且 1>=2 不成立；j=2 时 5<10 且 2>=2 成立，num[7] 变为 3；j=3 时 11 不小于 10，跳过；j=4 时 12 不小于 10，跳过；j=5 时 7<10 且 3>=3 成立，num[7] 变为 4；j=6 时 4<10 且 2>=4 不成立；num[7] 最终为 4。

至此，num 数组为 [1, 1, 2, 3, 4, 3, 2, 4]。最后循环求最大值，ans 为 4。程序输出 4，与正确答案一致。

从命题视角看，这道题的陷阱在于代码的嵌套结构和条件判断。学生如果只关注 height 的大小比较，而忽略 num[j] >= num[i] 这个关键条件，就会错误地认为只要前面有比当前小的数，就能接在后面，从而算出更大的长度。比如对于 height[5]=7，如果忽略 num 的更新，可能会误以为可以接在 height[3]=11 后面（虽然 11 不小于 7，但逻辑上容易混淆），或者误以为可以接在 height[4]=12 后面。实际上，num 的更新确保了只有在能形成更长上升子序列时才会更新。此外，LIS 不要求连续，但要求相对顺序不变，这也是学生容易混淆的点。如果题目改成求最长连续子序列，那就要用滑动窗口或前缀和，思路完全不同。

关于考频与趋势，根据题库统计，简单动态规划（LIS）共考过 94 题，覆盖 8 个考试级别（2009-2026）。逐年分布为：2009 年 2 题、2010 年 2 题、2013 年 2 题、2014 年 1 题、2015 年 1 题、2017 年 2 题、2018 年 1 题、2019 年 2 题、2021 年 1 题、2022 年 1 题、2023 年 15 题、2024 年 23 题、2025 年 25 题、2026 年 13 题。分赛事来看，GESP 六级考了 34 题、七级 27 题、八级 10 题，NOIP 提高组初赛 10 题，普及组初赛 1 题，CSP 入门级 5 题、提高级 4 题，GESP 五级 3 题。从数据看，2023 年后考频明显上升，2023-2026 年合计 76 题，远超之前的 32 题，说明动态规划是近年来的高频考点，尤其是 LIS 这种基础但易错题型，在初赛和 GESP 中反复出现。

预测未来，鉴于 2023-2026 年考频持续走高且分布均匀，LIS 及相关动态规划题（如最长不下降子序列、最长公共子序列、背包问题变种）在未来 1-2 年内仍将是初赛和 GESP 的重点。命题人可能会继续用代码阅读或填空的形式考察，也可能结合字符串或二维数组增加难度，但核心思想仍是状态转移和最优子结构。暂无足够依据预测具体的年份或题型变化，但可以肯定的是，扎实掌握 LIS 的动态规划解法是应对这类题目的关键。