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

6小时前比赛题解17

一、问题理解与算法思路

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

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义二维点结构体
struct Point {
    int x, y;
    // 重载比较运算符，用于排序
    bool operator<(const Point& other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

int main() {
    // 输入输出优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;  // 输入点数和可添加点数
    
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;  // 输入每个点的坐标
    }
    
    // 对点集进行排序：先按x升序，x相同则按y升序
    sort(points.begin(), points.end());
    
    // 动态规划表初始化
    // dp[i][j]表示以第i个点结尾，使用j个额外点时的最长序列长度
    vector<vector<int>> dp(n, vector<int>(k + 1, 1));
    int max_len = 1;  // 记录全局最大长度
    
    // 动态规划主循环
    for (int i = 0; i < n; ++i) {  // 遍历每个点作为终点
        for (int j = 0; j <= k; ++j) {  // 遍历可能的额外点数
            dp[i][j] = 1;  // 初始化为只包含当前点
            
            for (int prev = 0; prev < i; ++prev) {  // 检查所有可能的前驱点
                // 确保前驱点在当前点左下方
                if (points[prev].x > points[i].x || points[prev].y > points[i].y) {
                    continue;
                }
                
                // 计算两个点之间需要插入的点数
                int dx = points[i].x - points[prev].x;
                int dy = points[i].y - points[prev].y;
                int needed = dx + dy - 1;  // 需要插入的点数
                
                // 如果当前可用点数足够
                if (needed <= j) {
                    // 状态转移方程
                    dp[i][j] = max(dp[i][j], dp[prev][j - needed] + dx + dy);
                }
            }
            
            // 考虑使用剩余的k-j个点来延长序列
            max_len = max(max_len, dp[i][j] + (k - j));
        }
    }
    
    cout << max_len << endl;  // 输出结果
    return 0;
}