这里分别提供标准题解代码和用于生成测试数据的生成器代码。

1. 标准题解代码 (C++)

这是一个标准的 $O(N^2)$ 动态规划解法，代码结构清晰，适合作为参考答案。

// #include <iostream>
// #include <vector>
// #include <algorithm>
#include <bits/stdc++.h>

using namespace std;

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // dp[i] 表示以 a[i] 结尾的最长上升子序列长度
    // 初始化为 1，因为每个元素本身至少构成长度为 1 的子序列
    vector<int> dp(n, 1);
    
    int ans = 0;
    if (n > 0) ans = 1; // 只要有元素，至少长度为1

    for (int i = 0; i < n; i++) {
        // 回头看 i 之前的所有元素 j
        for (int j = 0; j < i; j++) {
            // 如果满足上升条件
            if (a[i] > a[j]) {
                // 尝试更新 dp[i]
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        // 更新全局最大值
        ans = max(ans, dp[i]);
    }

    cout << ans << endl;

    return 0;
}

2. 数据生成器 (Data Generator)

将以下代码保存为 generator.cpp 并编译运行。它会在当前目录下生成 1.in/1.out 到 10.in/10.out 共10组测试数据。

测试点覆盖策略：

• Test 1-2: 小规模随机数据 (基础逻辑验证)。
• Test 3: 严格递增序列 (答案应为 $N$)。
• Test 4: 严格递减序列 (答案应为 1)。
• Test 5: 全部相等序列 (答案应为 1，考察严格上升定义)。
• Test 6: 大量重复的小值随机序列 (考察相等值的处理)。
• Test 7: 中等规模随机。
• Test 8-10: 大规模随机数据 ($N=5000$)，测试性能与稳定性。

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <random>
#include <chrono>

using namespace std;

// ================== 核心解法 (用于生成 .out) ==================
int solve_lis(const vector<int>& a) {
    int n = a.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[i] > a[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

// ================== 数据生成工具 ==================

// 随机数生成器初始化
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

// 生成单个测试点
void generate_case(int case_id, int n, string type, int val_min = 1, int val_max = 1000000) {
    string in_filename = to_string(case_id) + ".in";
    string out_filename = to_string(case_id) + ".out";

    ofstream fout(in_filename);
    fout << n << endl;

    vector<int> arr(n);

    // 根据类型构造序列
    if (type == "random") {
        for (int i = 0; i < n; i++) {
            arr[i] = random_int(val_min, val_max);
        }
    } 
    else if (type == "increasing") {
        // 严格递增
        int start = random_int(1, 100);
        for (int i = 0; i < n; i++) {
            arr[i] = start + i;
        }
    }
    else if (type == "decreasing") {
        // 严格递减
        int start = val_max;
        for (int i = 0; i < n; i++) {
            arr[i] = start - i;
            if(arr[i] < 1) arr[i] = 1; // 防止越界
        }
    }
    else if (type == "equal") {
        // 全部相等
        int val = random_int(val_min, val_max);
        for (int i = 0; i < n; i++) {
            arr[i] = val;
        }
    }

    // 写入 .in 文件
    for (int i = 0; i < n; i++) {
        fout << arr[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();

    // 计算答案并写入 .out 文件
    int ans = solve_lis(arr);
    ofstream f_ans(out_filename);
    f_ans << ans << endl;
    f_ans.close();

    cout << "Generated Case " << case_id << ": N=" << n << " [" << type << "] -> Ans=" << ans << endl;
}

int main() {
    // 题目约束: N <= 5000, val <= 10^6
    
    // Test 1: 极小数据
    generate_case(1, 10, "random", 1, 20);

    // Test 2: 小数据
    generate_case(2, 50, "random", 1, 100);

    // Test 3: 边界 - 严格递增 (N=100)
    generate_case(3, 100, "increasing");

    // Test 4: 边界 - 严格递减 (N=100)
    generate_case(4, 100, "decreasing", 1, 5000);

    // Test 5: 边界 - 全部相等 (N=100)
    generate_case(5, 100, "equal");

    // Test 6: 边界 - 值域很小，大量重复 (N=500)
    generate_case(6, 500, "random", 1, 10);

    // Test 7: 中等规模 (N=1000)
    generate_case(7, 1000, "random", 1, 10000);

    // Test 8: 大规模随机 (N=5000)
    generate_case(8, 5000, "random", 1, 100000);

    // Test 9: 大规模随机 (N=5000, 值域打满)
    generate_case(9, 5000, "random", 1, 1000000);

    // Test 10: 大规模近乎递增 (N=5000)
    // 这里简单用 random 生成，概率上会有较长的 LIS，但主要测试大数据量下的运行时间
    generate_case(10, 5000, "random", 1, 500000);

    cout << "All 10 test cases generated successfully!" << endl;
    return 0;
}

你好！我是你的OI教练。很高兴看到你开始练习最基础的动态规划（DP）板子题。

这道题是下一题《合唱队形》的基石。如果说《合唱队形》是组合拳，那这道题就是基本功——直拳。掌握了它，很多序列相关的DP题你都能迎刃而解。

下面我们拿起笔，一起来拆解这道题。

第一部分：思路提示

1. 划重点： 题目有两个关键词：“按顺序”和“逐渐增大”。 这意味着我们不能打乱数组的顺序，只能从中挑出几个数，且后一个必须比前一个大。

2. 核心难点： 如果我们眼光只盯着“整个序列的最长长度”，会很难下手，因为组合太多了。 策略转换：不要一口气吃成胖子。我们能不能先算出“以第 1 个数结尾的最长上升子序列”、“以第 2 个数结尾的最长上升子序列”……直到算出“以第 $i$ 个数结尾的……”？

3. 关键提问： 假设你现在站在第 $i$ 个数字面前，想要知道以你（第 $i$ 个数）结尾的最长链条有多长。 你应该回头看谁？

• 你看向你前面的第 $j$ 个数字（$j < i$）。
• 如果你比他高（$a[i] > a[j]$），那你就可以接在他后面！
• 接在他后面，你的长度就是他的长度 $+ 1$。
• 既然前面可能有很多人都比你矮，你要选哪一个接在后面最划算？（提示：当然是选链条最长的那个）。

第二部分：预备知识点总结

要解决这道题，你需要掌握：

1. 一维数组：存储输入的序列。
2. 双重循环：
   • 外层循环遍历每一个位置 $i$（作为当前子序列的结尾）。
   • 内层循环遍历 $i$ 之前的所有位置 $j$（寻找可以拼接的前驱）。
3. 最值判断：使用 max 函数更新当前的最优解。
4. 动态规划思想（DP）：
   • 状态定义：$dp[i]$ 表示以第 $i$ 个元素结尾的最长上升子序列长度。
   • 无后效性：一旦 $dp[j]$ 算出来了，它的值就固定了，不会受后面的影响，我们可以放心使用。

第三部分：启发式教学 —— 草稿纸上的推演

现在，请在草稿纸上写下这行样例数据。我们要填满下方的 dp 表格。

数据序列 $a$：

下标 i :  1   2   3   4   5   6
数值 a :  1   2   4   1   3   4

DP 表格初始化： 每个人至少算 1 个（就是他自己），所以先把所有 $dp$ 值设为 1。

开始推演：

第 1 步：看 $i=1$（数值 1）

• 前面没人，没法接。
• $dp[1] = 1$。
• 草稿纸状态： 1

第 2 步：看 $i=2$（数值 2）

• 回头看 $j=1$（数值 1）：
  • $2 > 1$，可以接！
  • 接上后长度是 $dp[1] + 1 = 2$。
• $dp[2] = 2$。
• 草稿纸状态： 1 2

第 3 步：看 $i=3$（数值 4）

• 回头看 $j=1$（数值 1）：$4 > 1$，能接，长度 $1+1=2$。
• 回头看 $j=2$（数值 2）：$4 > 2$，能接，长度 $dp[2]+1 = 3$。
• 决策：3 比 2 大，所以选接在 $j=2$ 后面。
• $dp[3] = 3$。
• 草稿纸状态： 1 2 3

第 4 步：看 $i=4$（数值 1）

• 回头看 $j=1 \dots 3$：
  • $1$ 不大于 $1$（相等不行，要严格上升）。
  • $1$ 不大于 $2$。
  • $1$ 不大于 $4$。
• 一个都接不上，只能靠自己。
• $dp[4] = 1$。
• 草稿纸状态： 1 2 3 1

第 5 步：看 $i=5$（数值 3）

• 关键时刻！请你在纸上连线：
  • 能接在 $j=1$（数值1）后面吗？能 $\to$ 长度 $1+1=2$。
  • 能接在 $j=2$（数值2）后面吗？能 $\to$ 长度 $2+1=3$。
  • 能接在 $j=3$（数值4）后面吗？不能，3 < 4。
  • 能接在 $j=4$（数值1）后面吗？能 $\to$ 长度 $1+1=2$。
• 决策：最大的是 3（接在 $j=2$ 后）。
• $dp[5] = 3$。
• 草稿纸状态： 1 2 3 1 3

第 6 步：看 $i=6$（数值 4）

• 请自己尝试分析一下...
  • $4 > 1$ ($j=1$) $\to$ 长度 2
  • $4 > 2$ ($j=2$) $\to$ 长度 3
  • $4 > 4$ ($j=3$) $\to$ 不能
  • $4 > 1$ ($j=4$) $\to$ 长度 2
  • $4 > 3$ ($j=5$) $\to$ 长度 $dp[5] + 1 = 4$ $\leftarrow$ 发现最大值！
• $dp[6] = 4$。
• 草稿纸状态： 1 2 3 1 3 4

最后的陷阱与总结

填完表格后，我们得到了： dp 数组：1 2 3 1 3 4

教练提问： 答案是 $dp[n]$（最后一个元素）吗？ 看一眼我们的表格，虽然这里恰好 $dp[6]$ 是最大的，但假如序列后面跟了一个很小的数，比如 ... 4 0，那最后一个 dp 值就是 1。 所以，最终答案应该是 整个 dp 数组中的最大值。

代码逻辑框架（去填空吧）：

// 初始化 dp 数组全为 1
for (int i = 1; i <= n; i++) {
    // 这里的 j 就是“回头看”的过程
    for (int j = 1; j < i; j++) {
        if (a[i] > a[j]) {
            // 状态转移方程
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    // 别忘了在这个过程中记录 ans = max(ans, dp[i])
}

快去试试把代码写出来！