#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
int x;
int y;
};
int n,k;
node a[505];
int dp[505][105];
bool jl(node a,node b){
return abs(a.x-b.x)+abs(a.y-b.y);
}
bool cmp(node a,node b){
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=k;j++)
{
dp[i][j] = j+1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[j].y>a[i].y||a[j].x>a[i].x){
continue;
}
int dis=jl(a[i],a[j])-1;
for(int s=dis;s<=k;s++){
dp[i][s]=max(dp[i][s],dp[j][s-dis]+1+dis);
}
}
}
int ans=-1;
for(int i=1;i<=n;i++){
ans=max(ans,dp[i][k]);
}
cout<<ans;
return 0;
}
4 个赞
这题显然是个dp(好像还是个区d)
3 个赞