8276.[GESP样题 七级] 最长不下降子序列

算法思路

1. 问题分析

题目要求在有向无环图(DAG) 中寻找所有路径序列的最长不下降子序列(LIS)的最大长度。关键点：

• 图结构特性：DAG可用拓扑排序处理节点依赖关系
• 权值范围小：节点权值仅1~10，可设计状态压缩DP
• 状态设计：f[i][j]表示到达节点i时，以权值j结尾的LIS长度

2. 解决策略

1. 拓扑排序：处理节点依赖关系，确保状态转移时前驱节点已计算
2. 动态规划：
   • 状态转移1：当v的权值a[v]不小于u的权值i时：
     f[v][a[v]] = max(f[v][a[v]], f[u][i] + 1)
   • 状态转移2：直接继承前驱状态（维持当前权值序列）：
     f[v][j] = max(f[v][j], f[u][j])
3. 初始化：每个节点以自身权值结尾的LIS长度为1

3. 复杂度分析

• 时间复杂度：$O(10(n+m))$
  拓扑排序$O(n+m)$，每个节点处理时权值维度$O(10)$，每条边转移$O(10)$
• 空间复杂度：$O(n \times 10)$
  DP数组存储每个节点10种权值状态

代码实现

C++解法

cpp
复制
1#include <queue>
2#include <cstdio>
3#include <vector>
4using namespace std;
5
6vector<int> graph[100005]; // 邻接表存图
7int weight[100005];        // 节点权值
8int indegree[100005];      // 节点入度
9int dp[100005][11];        // DP状态数组
10
11int main() {
12    int n, m;
13    scanf("%d%d", &n, &m);
14    
15    // 读取节点权值
16    for (int i = 1; i <= n; i++) {
17        scanf("%d", &weight[i]);
18    }
19    
20    // 建图并统计入度
21    for (int i = 0; i < m; i++) {
22        int u, v;
23        scanf("%d%d", &u, &v);
24        graph[u].push_back(v);
25        indegree[v]++;
26    }
27    
28    queue<int> q;
29    // 初始化：入度为0的节点入队，设置初始DP状态
30    for (int i = 1; i <= n; i++) {
31        if (indegree[i] == 0) {
32            q.push(i);
33        }
34        dp[i][weight[i]] = 1; // 每个节点自身构成长度为1的序列
35    }
36    
37    // 拓扑排序
38    while (!q.empty()) {
39        int u = q.front();
40        q.pop();
41        
42        // 遍历当前节点的所有后继
43        for (int v : graph[u]) {
44            indegree[v]--; // O(1)操作
45            if (indegree[v] == 0) {
46                q.push(v);
47            }
48            
49            // 转移1：用u的权值更新v的权值位置
50            for (int i = 1; i <= weight[v]; i++) { // O(10)操作
51                if (dp[u][i] + 1 > dp[v][weight[v]]) {
52                    dp[v][weight[v]] = dp[u][i] + 1;
53                }
54            }
55            
56            // 转移2：直接继承u的状态
57            for (int j = 1; j <= 10; j++) { // O(10)操作
58                if (dp[u][j] > dp[v][j]) {
59                    dp[v][j] = dp[u][j];
60                }
61            }
62        }
63    }
64    
65    // 遍历所有节点和权值状态求最大值
66    int ans = 0;
67    for (int i = 1; i <= n; i++) {
68        for (int j = 1; j <= 10; j++) { // O(10*n)操作
69            if (dp[i][j] > ans) {
70                ans = dp[i][j];
71            }
72        }
73    }
74    printf("%d\n", ans);
75    return 0;
76}

代码解释：

1. 数据结构说明：
   • graph：邻接表存储图结构
   • indegree：记录节点入度用于拓扑排序
   • dp[i][j]：关键DP状态数组
2. 核心逻辑：
   • 拓扑排序：确保节点按依赖顺序处理
   • 双重状态转移：
     • 转移1：用前驱节点较小权值更新当前节点权值位置
     • 转移2：直接继承前驱节点所有状态
3. 边界处理：
   • 入度为0的节点初始化入队
   • 每个节点自身权值状态初始化为1

Python3解法

python
复制
1from collections import deque
2
3def main():
4    import sys
5    data = sys.stdin.read().split()
6    # 解析输入数据
7    n = int(data[0])
8    m = int(data[1])
9    weights = [0] + list(map(int, data[2:2+n]))
10    
11    # 初始化图结构和入度数组
12    graph = [[] for _ in range(n+1)]
13    indegree = [0] * (n+1)
14    idx = 2 + n
15    for _ in range(m):
16        u = int(data[idx])
17        v = int(data[idx+1])
18        idx += 2
19        graph[u].append(v)
20        indegree[v] += 1
21    
22    # 初始化DP数组（二维列表）
23    dp = [[0] * 11 for _ in range(n+1)]  # 权值范围1~10
24    
25    # 拓扑排序队列初始化
26    q = deque()
27    for i in range(1, n+1):
28        if indegree[i] == 0:
29            q.append(i)
30        dp[i][weights[i]] = 1  # 初始状态
31    
32    # 拓扑排序过程
33    while q:
34        u = q.popleft()
35        for v in graph[u]:
36            indegree[v] -= 1  # O(1)操作
37            if indegree[v] == 0:
38                q.append(v)
39            
40            # 转移1：更新v节点自身权值位置
41            for val in range(1, weights[v] + 1):  # O(10)操作
42                if dp[u][val] + 1 > dp[v][weights[v]]:
43                    dp[v][weights[v]] = dp[u][val] + 1
44            
45            # 转移2：继承u的所有状态
46            for j in range(1, 11):  # O(10)操作
47                if dp[u][j] > dp[v][j]:
48                    dp[v][j] = dp[u][j]
49    
50    # 全局最大值求解
51    ans = 0
52    for i in range(1, n+1):
53        for j in range(1, 11):  # O(10*n)操作
54            if dp[i][j] > ans:
55                ans = dp[i][j]
56    print(ans)
57
58if __name__ == "__main__":
59    main()

代码解释：

1. 与C++的差异：
   • 使用deque实现队列而非STL
   • 二维DP数组通过列表嵌套实现
   • 动态解析输入数据而非直接scanf
2. Python特性：
   • 使用sys.stdin.read()批量读取输入提升效率
   • 通过切片操作高效解析输入数据
   • 嵌套列表推导式初始化DP数组
3. 关键逻辑：
   • 拓扑排序与状态转移逻辑与C++完全一致
   • 权值范围硬编码为1~10符合题目约束

复杂度对比

选择建议：

1. 竞赛场景：优先选择C++实现，尤其当$n$接近$10^5$时
2. 开发效率：Python更适合作答验证和原型设计
3. 内存敏感：C++内存控制更精确，Python可能因对象开销超出限制