P8816 [CSP-J 2022] 上升点列
欧几里得距离\(h=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}\) 。
横坐标、纵坐标值均单调不减，A点可向上和向右。
①不连接，用上所有点，序列长度为\(j + 1\)。
②从A点向前枚举
(1)判断点是否合法 (2)所用点\(j \le K\).
01背包与最长子序列结合：
\(f[i][j]\)表示从第i个点开始向前枚举所用点\(j \le K\).，最长合法子序列的值。
d为两点之间需要添加的点。
状态转移 \(f[i][j]= \max (f[i][j],f[r][j-d]+d+1)\)
小寄巧 pair排序:默认第一关键字，然后是第二关键字升序
#include <bits/stdc++.h>
using namespace std;
const int N=510;
int n,k,f[N][N],x,y;
pair<int,int> PII[N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>x>>y;
PII[i]=make_pair(x,y);
}
sort(PII+1,PII+n+1);//升序排序
int ans=0;
for(int i=1;i<=n;i++){
int xi=PII[i].first,yi=PII[i].second;
for(int j=0;j<=k;j++){
f[i][j]=j+1;//不连接
for(int r=1;r<i;r++){
int xr=PII[r].first,yr=PII[r].second;
if(xr<=xi&&yr<=yi){//判断是否为合法的点
int d=xi-xr+yi-yr-1;
if(d<=j) f[i][j]=max(f[i][j],f[r][j-d]+d+1);
}
}
}
for(int j=0;j<=k;j++) ans=max(ans,f[i][j]);
}
cout<<ans;
return 0;
}