这是一个功能完备的 C++ 数据生成器。它集成了标准的拓扑排序+DP解题逻辑（用于生成正确的 .out 文件）和针对题目三个子任务（Subtask）设计的图结构生成逻辑（用于生成 .in 文件）。

运行此代码将自动在当前目录下生成 1.in/1.out 到 10.in/10.out。

数据生成策略说明

• 测试点 1-3 (Subtask 1)：$N \le 1000$，图是一条链 ($1 \to 2 \to \dots \to N$)。覆盖了基础逻辑。
• 测试点 4-7 (Subtask 2)：$N$ 逐渐增大到 $10^5$，点权 $A_i \le 2$。考察在权值种类很少时的处理能力。
• 测试点 8-10 (Subtask 3)：$N, M$ 达到 $10^5$，点权 $1 \le A_i \le 10$，图结构复杂。
  • 点 9 特意构造了利于形成长不下降序列的权重分布，用于压力测试 DP 的传递性。
  • 点 10 为大规模随机 DAG。

C++ 数据生成器代码

/**
 * P10287 [GESP样题 七级] 最长不下降子序列 - 数据生成器
 * 功能：生成 1.in/1.out ~ 10.in/10.out
 * 包含：标准解法逻辑 + 针对三个子任务的数据构造
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <set>
#include <random>
#include <ctime>

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (用于生成 .out)
// ==========================================
const int MAXVAL = 11; // 权值范围 1-10

struct Solver {
    int n, m;
    vector<int> A;
    vector<vector<int>> adj;
    vector<int> in_degree;
    // dp[u][v] 表示在节点 u 结束，且子序列结尾数值为 v 的最大长度
    vector<vector<int>> dp;

    int solve(int _n, int _m, const vector<int>& _A, const vector<pair<int, int>>& edges) {
        n = _n;
        m = _m;
        A = _A; // A 下标从 1 开始 (第0位是占位符)
        
        // 初始化容器
        adj.assign(n + 1, vector<int>());
        in_degree.assign(n + 1, 0);
        dp.assign(n + 1, vector<int>(MAXVAL, 0));
        
        // 建图
        for (const auto& edge : edges) {
            adj[edge.first].push_back(edge.second);
            in_degree[edge.second]++;
        }

        // 拓扑排序准备
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }

        int final_ans = 0;

        // 拓扑排序 + DP
        while (!q.empty()) {
            int u = q.front();
            q.pop();

            int val_u = A[u]; 
            
            // 核心步骤 A: 尝试将 A[u] 加入子序列
            // 在 u 当前继承到的状态中，找一个结尾值 <= val_u 的最大长度
            int max_len_before = 0;
            for (int v = 1; v <= val_u; ++v) {
                max_len_before = max(max_len_before, dp[u][v]);
            }
            dp[u][val_u] = max(dp[u][val_u], max_len_before + 1);

            // 更新全局答案
            for (int v = 1; v <= 10; ++v) {
                final_ans = max(final_ans, dp[u][v]);
            }

            // 核心步骤 B: 向后传递状态
            for (int v_node : adj[u]) {
                for (int k = 1; k <= 10; ++k) {
                    dp[v_node][k] = max(dp[v_node][k], dp[u][k]);
                }
                
                in_degree[v_node]--;
                if (in_degree[v_node] == 0) {
                    q.push(v_node);
                }
            }
        }
        return final_ans;
    }
};

// ==========================================
// Part 2: 数据构造逻辑 (生成 .in)
// ==========================================
mt19937 rng((unsigned)time(0));

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

void makeData(int id) {
    string inName = to_string(id) + ".in";
    string outName = to_string(id) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    int N, M;
    vector<int> A; // 1-based padding
    vector<pair<int, int>> edges;

    // 根据测试点 ID 配置参数
    if (id <= 3) {
        // Subtask 1: 链状图, N <= 1000
        if (id == 1) N = 10;
        else if (id == 2) N = 100;
        else N = 1000;
        
        M = N - 1;
        // 生成链: 1->2->...->N
        for(int i=1; i<N; ++i) edges.push_back({i, i+1});
        
        // 权值 1-10
        A.push_back(0); 
        for(int i=1; i<=N; ++i) A.push_back(randInt(1, 10));

    } else if (id <= 7) {
        // Subtask 2: N <= 10^5, A_i <= 2
        // id 4: 小规模测试
        // id 5: 中等规模
        // id 6, 7: 大规模
        if (id == 4) N = 100;
        else if (id == 5) N = 1000;
        else N = 100000;

        M = min((long long)N * 2, 100000LL); 
        if (id == 7) M = 100000; // 满边

        // DAG 生成: 保证 u < v 即可无环
        set<pair<int,int>> edgeSet;
        // 构造主干以保证深度
        for(int i=1; i<N; ++i) {
             if (randInt(0, 1)) edgeSet.insert({i, i+1});
        }
        
        // 随机加边
        while(edgeSet.size() < M) {
            int u = randInt(1, N-1);
            int v = randInt(u + 1, min(N, u + 50)); // 连向后面不远处的点，促进长路径
            if (u == v) continue;
            edgeSet.insert({u, v});
        }
        edges.assign(edgeSet.begin(), edgeSet.end());
        M = edges.size();

        // 权值 1-2
        A.push_back(0);
        for(int i=1; i<=N; ++i) A.push_back(randInt(1, 2));

    } else {
        // Subtask 3: N <= 10^5, A_i <= 10
        N = 100000;
        M = 100000;
        
        set<pair<int,int>> edgeSet;
        
        // 构造一条长主干
        for(int i=1; i<N; ++i) {
            edgeSet.insert({i, i+1});
        }
        
        // 增加跳跃边
        while(edgeSet.size() < M) {
            int u = randInt(1, N-5);
            int v = randInt(u+2, min(N, u+20)); 
            edgeSet.insert({u, v});
        }
        edges.assign(edgeSet.begin(), edgeSet.end());
        
        // 权值 1-10
        A.push_back(0);
        if (id == 9) {
             // 特殊构造: 循环递增权值 (1,2,3...10,1,2...) 以最大化 LIS 长度
             for(int i=1; i<=N; ++i) A.push_back((i % 10) + 1);
        } else {
             // 完全随机权值
             for(int i=1; i<=N; ++i) A.push_back(randInt(1, 10));
        }
    }

    // 写入输入文件
    fin << N << " " << M << endl;
    for(int i=1; i<=N; ++i) fin << A[i] << (i==N ? "" : " ");
    fin << endl;
    
    // 打乱边的顺序输出 (虽然拓扑结构 u<v 不变，但输入顺序打乱)
    vector<pair<int,int>> shuffled_edges = edges;
    shuffle(shuffled_edges.begin(), shuffled_edges.end(), rng);
    
    for(const auto& e : shuffled_edges) {
        fin << e.first << " " << e.second << endl;
    }

    // 运行求解并写入输出文件
    Solver solver;
    int ans = solver.solve(N, M, A, shuffled_edges);
    fout << ans << endl;

    fin.close();
    fout.close();
    cout << "Generated Case " << id << " N=" << N << " M=" << M << endl;
}

int main() {
    for(int i=1; i<=10; ++i) {
        makeData(i);
    }
    cout << "All data generated successfully." << endl;
    return 0;
}

你好！我是你的OI教练。很高兴能带你攻克这道 GESP 七级的图论+动态规划题目。

这道题《最长不下降子序列》乍一看有点像经典的 LIS（最长上升/不下降子序列）问题，但它发生在一个**DAG（有向无环图）**上，而且路径是不固定的。

别慌，我们先拿出草稿纸，抓住题目的“七寸”——那个特别小的数据范围。

1. 读题关键词：你的“雷达”响了吗？

读题时，请务必圈出以下几个决定解题策略的关键信息：

1. “有向无环图 (DAG)”：
   • 这暗示我们可以使用拓扑排序来处理节点的遍历顺序。因为在 DAG 上，状态的转移是有明确方向的，不会有环造成的死循环。
2. “路径上的经过节点的先后顺序”：
   • 说明我们的 DP 状态必须沿着边的方向传递。
3. “$A_i \le 10$”：
   • 这是本题最大的破局点！
   • 通常 LIS 问题的数值范围很大，我们关注的是长度。但这里数值只有 1 到 10。
   • 这意味着我们可以把数值直接写进 DP 的状态维度里，而不用担心空间爆炸。

2. 预备知识点

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

• 拓扑排序 (Topological Sort)：用于在 DAG 上确定处理顺序（Kahn 算法）。
• 动态规划 (DP)：理解状态转移。
• 最长不下降子序列 (LIS)：基本概念。

3. 启发式教学：草稿纸上的推演

我们以前做数组的 LIS 时，定义 $dp[i]$ 是以第 $i$ 个数结尾的 LIS 长度。 但在图上，走到节点 $u$ 时，可能有无数条路径。我们怎么记住前面的状态呢？

利用 $A_i \le 10$ 的特性： 不管前面的路径怎么走，对于后续的决策，我们只需要知道两件事：

1. 当前已经凑出的 LIS 长度是多少？
2. 当前 LIS 的结尾数值是多少？（因为下一个数必须 $\ge$ 这个结尾数值）。

状态定义： 设 $dp[u][v]$ 表示：从任意起点走到节点 $u$，并且构造出的不下降子序列以数值 $v$ 结尾时，能达到的最大长度。

• $u$ 的范围是 $1 \sim 10^5$。
• $v$ 的范围是 $1 \sim 10$。
• 数组大小约 $10^6$，完全存得下！

转移逻辑（以节点 $u$ 为例）： 假设我们正在处理节点 $u$，它的权值是 $A_u$。 $u$ 的状态来源于所有指向它的父节点 $p$。

1. 继承（不选 $A_u$）：

   • 虽然人走到了 $u$，但我们不把 $A_u$ 加入子序列。
   • 这时状态直接从父节点拷贝过来（取最大值）：$dp[u][k] = \max(dp[p][k])$。这一步其实在拓扑排序的“推”过程中完成。

2. 选择（选 $A_u$）：

   • 我们要把 $A_u$ 接在某个子序列后面。
   • 这个子序列的结尾值 $k$ 必须满足 $k \le A_u$。
   • 我们找一个最大的前驱长度：$len = 1 + \max_{1 \le k \le A_u} (dp[u][k])$。
   • 注意：这里的 $dp[u][k]$ 已经是综合了所有父节点传过来的数据的最优值。
   • 更新：$dp[u][A_u] = \max(dp[u][A_u], len)$。

处理流程：

1. 建图，统计入度。
2. 将所有入度为 0 的点放入队列。
3. 当队列不为空：
   • 取出节点 $u$。
   • 计算选 $A_u$ 的情况：遍历 $k$ 从 1 到 $A_u$，找到最长的那个接上去，更新 $dp[u][A_u]$。
   • 向后传递：遍历 $u$ 的所有邻居 $v$，把 $dp[u][1\dots10]$ 的值尝试更新到 $dp[v][1\dots10]$ 中（取 max）。
   • $v$ 的入度减 1，如果为 0 入队。

4. 标准代码 (NOIP C++14)

/**
 * 题目：P10287 [GESP样题 七级] 最长不下降子序列
 * 考点：拓扑排序、动态规划、DAG上的DP
 * 时间复杂度：O(M * 10)，因为 M <= 10^5，常数极小，非常快。
 */

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int MAXVAL = 11; // 权值范围 1-10

int n, m;
int A[MAXN]; // 存储点权
vector<int> adj[MAXN]; // 邻接表
int in_degree[MAXN]; // 入度

// dp[u][v] 表示在节点 u 结束，且子序列结尾数值为 v 的最大长度
// 注意：这里的“在 u 结束”指的是路径走到了 u，子序列的最后一个元素就是 v
int dp[MAXN][MAXVAL]; 

void solve() {
    // 1. 输入处理
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        in_degree[v]++;
    }

    // 2. 拓扑排序初始化
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    int final_ans = 0;

    // 3. 拓扑排序 + DP
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 核心步骤 A：考虑将当前节点 A[u] 加入到子序列中
        // 我们需要在 u 节点目前继承到的所有状态中，找一个结尾值 <= A[u] 的最长子序列
        int val_u = A[u];
        int max_len_before = 0;
        for (int v = 1; v <= val_u; ++v) {
            max_len_before = max(max_len_before, dp[u][v]);
        }
        
        // 加上 A[u] 自己，长度 + 1，更新到以 val_u 结尾的状态中
        dp[u][val_u] = max(dp[u][val_u], max_len_before + 1);

        // 统计当前节点所有可能状态的最大值到全局答案
        for (int v = 1; v <= 10; ++v) {
            final_ans = max(final_ans, dp[u][v]);
        }

        // 核心步骤 B：将当前节点 u 的所有状态“推”给邻居 v
        // 相当于邻居 v 继承了 u 路径上的所有可能性（但不一定要选 v 的点权，那是 v 处理时的事）
        for (int v_node : adj[u]) {
            for (int k = 1; k <= 10; ++k) {
                dp[v_node][k] = max(dp[v_node][k], dp[u][k]);
            }
            
            in_degree[v_node]--;
            if (in_degree[v_node] == 0) {
                q.push(v_node);
            }
        }
    }

    cout << final_ans << endl;
}

int main() {
    // IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    solve();
    
    return 0;
}

5. 易错点总结

1. DP 状态的理解：
   • $dp[u][v]$ 到底包不包含 $A_u$？
   • 在代码逻辑中，当我们将父节点的状态推给 $u$ 时，$dp[u][v]$ 还没包含 $A_u$。
   • 当我们执行 dp[u][val_u] = max(..., ...) 后，状态更新为包含了 $A_u$。
   • 同时，$dp[u][other]$ 保持原样，代表“虽然路过了 $u$，但我没选 $A_u$ 进子序列，还是沿用之前的结尾值”。这完美覆盖了“跳过节点”的情况。
2. 入度统计：
   • 一定要在输入边的时候统计入度，否则拓扑排序无法开始。
3. 常数优化：
   • 由于 $N, M$ 达到 $10^5$，内层循环虽然只有 10 次，但如果不加 IO 优化 (ios_base::sync_with_stdio(false))，在极端数据下可能会稍慢，建议加上。

祝你通过这道题，彻底掌握 DAG 上的 DP 技巧！加油！