2022 CSP-J 上升点序（洛谷P8816）解题报告：动态规划求解最长上升序列
4周前 (06-21)
一、题目解读
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问题的建模思路，对算法竞赛中类似题目具有重要参考价值。
原创内容 转载请注明出处
