动态规划经典应用：2022年CSP-J上升点列问题详解与代码实现

19339201706

一、问题理解与算法思路

题目要求在一组二维坐标点中，找出最长的严格递增序列（x和y都严格递增），允许插入最多k个额外点来连接不相邻的点。这个问题可以抽象为在二维平面上的路径规划问题，需要找到最优的连接方式。

二、完整代码实现（带详细注释）

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. // 定义二维点结构体
   
7. struct Point {
   
8.     int x, y;
   
9.     // 重载比较运算符，用于排序
   
10.     bool operator<(const Point& other) const {
    
11.         return x < other.x || (x == other.x && y < other.y);
    
12.     }
    
13. };
    
14. 
    
15. int main() {
    
16.     // 输入输出优化
    
17.     ios::sync_with_stdio(false);
    
18.     cin.tie(nullptr);
    
19.    
    
20.     int n, k;
    
21.     cin >> n >> k;  // 输入点数和可添加点数
    
22.    
    
23.     vector<Point> points(n);
    
24.     for (int i = 0; i < n; ++i) {
    
25.         cin >> points[i].x >> points[i].y;  // 输入每个点的坐标
    
26.     }
    
27.    
    
28.     // 对点集进行排序：先按x升序，x相同则按y升序
    
29.     sort(points.begin(), points.end());
    
30.    
    
31.     // 动态规划表初始化
    
32.     // dp[i][j]表示以第i个点结尾，使用j个额外点时的最长序列长度
    
33.     vector<vector<int>> dp(n, vector<int>(k + 1, 1));
    
34.     int max_len = 1;  // 记录全局最大长度
    
35.    
    
36.     // 动态规划主循环
    
37.     for (int i = 0; i < n; ++i) {  // 遍历每个点作为终点
    
38.         for (int j = 0; j <= k; ++j) {  // 遍历可能的额外点数
    
39.             dp[i][j] = 1;  // 初始化为只包含当前点
    
40.             
    
41.             for (int prev = 0; prev < i; ++prev) {  // 检查所有可能的前驱点
    
42.                 // 确保前驱点在当前点左下方
    
43.                 if (points[prev].x > points[i].x || points[prev].y > points[i].y) {
    
44.                     continue;
    
45.                 }
    
46.                
    
47.                 // 计算两个点之间需要插入的点数
    
48.                 int dx = points[i].x - points[prev].x;
    
49.                 int dy = points[i].y - points[prev].y;
    
50.                 int needed = dx + dy - 1;  // 需要插入的点数
    
51.                
    
52.                 // 如果当前可用点数足够
    
53.                 if (needed <= j) {
    
54.                     // 状态转移方程
    
55.                     dp[i][j] = max(dp[i][j], dp[prev][j - needed] + dx + dy);
    
56.                 }
    
57.             }
    
58.             
    
59.             // 考虑使用剩余的k-j个点来延长序列
    
60.             max_len = max(max_len, dp[i][j] + (k - j));
    
61.         }
    
62.     }
    
63.    
    
64.     cout << max_len << endl;  // 输出结果
    
65.     return 0;
    
66. }

复制代码

三、算法核心解析

• 预处理排序：将点按x坐标升序排列，x相同时按y升序排列，确保后续处理的有序性。
• 动态规划状态定义：
  
  
  • dp[j]：表示以第i个点结尾，使用j个额外点时的最长序列长度
  • 初始状态：每个点单独构成序列，长度为1
    
    
• 状态转移过程：
  
  
  • 对于每个点i，检查所有可能的前驱点prev
  • 确保prev点在i点的左下方（x和y都更小）
  • 计算两点间需要插入的点数needed = dx + dy - 1
  • 如果可用点数j >= needed，则更新dp[j]
    
    
• 全局最大值更新：
  
  
  • 考虑使用剩余的k-j个点来延长当前序列
  • 实时更新max_len记录全局最大值
    
    

四、复杂度分析与优化

• 时间复杂度：O(n²k)
• 空间复杂度：O(nk)
• 可能的优化方向：
  
  
  • 预处理点对距离
  • 使用单调性优化减少内层循环
  • 空间优化为滚动数组
    
    

五、学习要点总结

• 理解动态规划在多维状态下的应用
• 掌握二维问题的状态定义技巧
• 学会处理带约束条件的动态规划问题
• 理解排序预处理在算法中的重要性
  
  

来源：动态规划经典应用：2022年CSP-J上升点列问题详解与代码实现