P8816 [CSP-J 2022] 上升点列
题目大意
给定 \(n\) 个点，你可以任意添加 \(k\) 个点，从中选择若干点使得序列中任意相邻两点间的欧几里得距离恰好为 \(1\) 而且横坐标、纵坐标值均单调不减 。换言之，求二维最长上升子序列。
solution：
很容易想到动态规划，根据最长上升子序列的套路，可以枚举点 \(i\) ，再枚举之前出现的点 \(j\) ，计算距离 \(d\) ，判断是否可以添加 \(d\) 个点使得连在一起。此时就需要已经添加的点的个数 \(k\) 。那么不妨枚举到 \(i\) 点，已经添加的点的个数 \(k\) 。那么状态转移方程为：
\[f_{i,k}=\text{max}(f_{i,k},f_{j,k-d}+d+1) \]细节处理：
- 排序 \(x\) 优先，其次 \(y\) 。
- 对于枚举 \(k\) 的初始化，易知可以直接在前添加 \(k\) 个点。
代码
summary>#include<cstdio>
#include<algorithm>
using namespace std;
const int N=550;
int f[N][N];
struct node{
int x,y;
}p[N];
bool em(node a,node b){
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
int main(){
int n,K; scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
sort(p+1,p+n+1,em);
for(int i=1;i<=n;i++){
for(int k=0;k<=K;k++){
f[i][k]=k+1;
for(int j=1;j<i;j++){
if(p[j].x>p[i].x||p[j].y>p[i].y) continue;
int d=p[i].x-p[j].x+p[i].y-p[j].y-1;
if(k<d) continue;
f[i][k]=max(f[i][k],f[j][k-d]+d+1);
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int k=0;k<=K;k++){
ans=max(ans,f[i][k]);
}
}
printf("%d",ans);
return 0;
}
End
题外话：
回归的第一篇题解。
好久不写博客，略显手生。