2022 CSP-J 上升点序（洛谷P8816）解题报告：动态规划求解最长上升序列

一、题目解读

2022年CSP-J题目“上升点序”（洛谷P8816）要求给定一个平面点集，每个点的坐标(x,y)均为整数。题目需要构造一个最长的上升序列，序列中相邻点的坐标满足x和y均严格递增。允许使用额外的点（不超过k个）来连接原序列中的点，最终输出最长上升序列的长度。关键点在于如何高效利用额外点来扩展序列，同时保证上升性。

二、解题思路

作者采用动态规划（DP）解决该问题。核心思想是将问题分解为子问题，通过状态转移计算最长序列。定义二维DP数组dp[i][j]表示以第i个点结尾，使用j个额外点时的最长序列长度。通过遍历所有可能的“前驱点”，计算插入额外点的数量，从而更新状态。

三、解题步骤

1. 输入与预处理：读入n个点坐标，按(x,y)升序排序（确保后续DP顺序依赖）。

2. 动态规划初始化：dp[i][j]初始化为1（每个点自身构成长度为1的序列）。

3. 状态转移：

    遍历前驱点prev，若prev在点i的左下方，计算需插入的点数needed = dx + dy - 1（由斜率公式推导）。

    若needed ≤ j，更新dp[i][j] = max(dp[i][j], dp[prev][j-needed] + dx + dy)，即利用剩余额外点延长序列。

4. 结果优化：考虑剩余额外点（k-j）对序列的延长，更新全局最大值max_len。

5. 输出结果：最终最长序列长度。

四、代码与注释

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

// 定义点结构，按(x,y)升序排序
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;
    }
    sort(points.begin(), points.end()); // 排序，保证DP顺序依赖

    // 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; // 初始化为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);
                }
            }
            max_len = max(max_len, dp[i][j] + (k - j)); // 考虑剩余额外点延长
        }
    }
    
    cout << max_len << endl;
    return 0;
}

五、总结

该解法巧妙利用动态规划解决带额外点的最长上升序列问题。通过排序预处理、斜率推导的插入点数计算，以及状态转移优化，将复杂问题转化为可迭代的子问题。代码结构清晰，时间复杂度O(n²k)，适合竞赛场景。掌握此类DP问题的建模思路，对算法竞赛中类似题目具有重要参考价值。