[CSP-J 2022] 上升点列 题解
2026-08-09 09:07:21
发布于：广东
[CSP-J 2022] 上升点列 题解
一、先理解题目（不要急着抽象）
【简单理解】
这道题其实是在解决：
平面上有一些已经给好的点，我们还可以自己补 k 个整数点。
我们要从这些点里选出一串点，要求每一步只能：
向右走 1 格
或者向上走 1 格
也就是说，相邻两个点只能是：
(x,y) -> (x+1,y)
或
(x,y) -> (x,y+1)
最后要求这串点尽量长。
题目中的东西：
n：原来给定的点数；k：最多可以补的点数；(x[i],y[i])：第i个原有点的位置；- 最后要求：最长能组成多少个点。
二、题意抽象（从故事变成数学问题）
【抽象之后】
给定：
一些二维整数点，以及最多 k 个可以自由添加的点。
要求：
选出一个序列，使得每一步横坐标或纵坐标增加 1，另一个坐标不变。
本质：
如果一个点要接到另一个点后面，后面的点必须在它的右上方向。
也就是：
x[j]<=x[i] 且 y[j]<=y[i]
从 j 走到 i 的最短步数是：
dis=(x[i]-x[j])+(y[i]-y[j])
中间缺的点数是：
need=dis-1
三、思考如何解决（先讲思考过程）
1. 最直接的方法是什么？
最直接的方法是：
尝试所有选点顺序，并尝试在哪里补点。
这样不行，因为点的选择方式很多，补点位置也很多。
2. 观察题目特点
我们发现：
如果最后一个原有点确定了，前面的最优答案可以继续接过来。
而且补了多少个点也很重要。
例如同样以某个点结尾：
- 用了
2个补点； - 用了
5个补点；
后面还能继续补的数量不同，所以不能混在一起。
3. 得出算法选择
因为一个大问题可以由前面的小问题推出来，所以使用动态规划。
动态规划可以理解成：
先把“以某个点结尾”的小答案算出来，再用这些小答案推出更大的答案。
四、算法核心思想（重点讲理解）
状态
设：
dp[i][j]
表示：
以第 i 个原有点作为最后一个原有点，并且已经用了 j 个补点时，最多能组成多少个点。
每个字母的意思：
i：最后停在哪个原有点；j：已经用了多少个自己补的点；dp[i][j]：这种情况下点列的最大长度。
为什么是二维？
因为只知道“最后是第几个点”不够，还要知道已经用了多少个补点。
转移
假设要从原有点 pre 接到原有点 i。
必须满足：
x[pre]<=x[i] 且 y[pre]<=y[i]
这样才能只向右或向上走。
两点之间最少要走：
dis=(x[i]-x[pre])+(y[i]-y[pre])
中间要补：
need=dis-1
个点。
如果之前用了 j-need 个补点，现在再补 need 个，就一共用了 j 个。
所以可以更新：
dp[i][j]=max(dp[i][j],dp[pre][j-need]+dis)
为什么加的是 dis？
从 pre 走到 i 一共经过 dis 条边，会新增加 dis 个点，包括中间补的点和终点 i。
初始化
如果只以第 i 个点为结尾，前面放一些自己补的点，也能形成点列。
所以：
dp[i][j]=j+1
表示 j 个补点加上第 i 个原有点。
答案
点列最后不一定停在原有点后就结束。
如果还剩一些补点，也可以继续往右或往上接在后面。
所以答案是：
max(dp[i][j]+k-j)
五、用简单例子模拟算法过程
假设：
k=2
点 A=(1,1)
点 B=(3,2)
从 A 到 B：
dis=(3-1)+(2-1)=3
说明要走 3 步。
路径可以是：
(1,1)->(2,1)->(3,1)->(3,2)
中间缺了：
need=dis-1=2
个点。
如果 dp[A][0]=1，表示只选了 A。
用了 2 个补点接到 B 后：
dp[B][2]=dp[A][0]+3=4
这 4 个点就是：
A + 两个补点 + B
六、复杂度分析
我们枚举：
- 当前结尾点
i； - 前一个原有点
pre； - 已经用了多少补点
j。
所以时间复杂度是：
O(n^2*k)
因为 n<=500,k<=100，可以通过。
空间复杂度：
O(n*k)
七、代码实现思路
需要的变量：
n,k：原有点数、可补点数；a[i].x,a[i].y：第i个点的坐标；dp[i][j]：以第i个点结尾，用了j个补点的最长长度；dis：两个点之间最少走几步；need：两个点中间要补几个点。
部分解：k=0
不能补点时，两个原有点必须刚好相邻才能接上。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510;
struct node{
int x,y;
}a[N];
int dp[N];
bool cmp(node A,node B){
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
void solve(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
int ans=1;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int pre=1;pre<i;pre++){
int dis=a[i].x-a[pre].x+a[i].y-a[pre].y;
if(a[pre].x<=a[i].x&&a[pre].y<=a[i].y&&dis==1){
dp[i]=max(dp[i],dp[pre]+1);
}
}
ans=max(ans,dp[i]);
}
cout<<ans<<"\n";
}
signed main(){
int _=1;
while(_--) solve();
}
正解代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510,K=110;
struct node{
int x,y;
}a[N];
int dp[N][K];
bool cmp(node A,node B){
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
void solve(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++) dp[i][j]=j+1;
for(int pre=1;pre<i;pre++){
if(a[pre].x>a[i].x||a[pre].y>a[i].y) continue;
int dis=a[i].x-a[pre].x+a[i].y-a[pre].y;
int need=dis-1;
for(int j=need;j<=k;j++){
dp[i][j]=max(dp[i][j],dp[pre][j-need]+dis);
}
}
for(int j=0;j<=k;j++){
ans=max(ans,dp[i][j]+k-j);
}
}
cout<<ans<<"\n";
}
signed main(){
int _=1;
while(_--) solve();
}
八、代码逐步解释
先排序：
sort(a+1,a+n+1,cmp);
这样枚举 pre<i 时，比较方便找到可能在前面的点。
核心转移：
if(a[pre].x>a[i].x||a[pre].y>a[i].y) continue;
如果 pre 不在 i 的左下方向，就不能只向右或向上走到 i。
int need=dis-1;
两端点已经存在，所以中间只需要补 dis-1 个点。
dp[i][j]=max(dp[i][j],dp[pre][j-need]+dis);
表示从 pre 的最优点列接到 i，中间补点，并把新经过的点数加上。
九、易错点总结
- 忘记排序，导致前后顺序不好处理。
- 没判断
x,y都不减，就可能走出“向左”或“向下”的路线。 - 把补点数写成
dis，正确是dis-1。 - 忘记初始化
dp[i][j]=j+1。 - 忘记最后加上剩余补点
k-j。
十、最后总结解题方法
这道题考察：
动态规划、二维状态设计、曼哈顿距离。
看到这类题：
第一步：
先判断两个点能不能接上，也就是能不能只向右或向上走。
第二步：
计算两个点之间缺多少补点。
第三步：
发现“用了多少补点”会影响后面，所以状态要多一维。
第四步：
用前面的点列更新当前点列，最后把剩余补点接到末尾。
这里空空如也
有帮助，赞一个