CSP-J 2022 T4 上升点列

· · 个人记录

[CSP-J 2022] 上升点列

题目描述

在一个二维平面内，给定 n 个整数点 (x_i, y_i)，此外你还可以自由添加 k 个整数点。

你在自由添加 k 个点后，还需要从 n + k 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且横坐标、纵坐标值均单调不减，即 x_{i+1} - x_i = 1, y_{i+1} = y_i 或 y_{i+1} - y_i = 1, x_{i+1} = x_i。请给出满足条件的序列的最大长度。

输入格式

第一行两个正整数 n, k 分别表示给定的整点个数、可自由添加的整点个数。

接下来 n 行，第 i 行两个正整数 x_i, y_i 表示给定的第 i 个点的横纵坐标。

输出格式

输出一个整数表示满足要求的序列的最大长度。

样例 #1

样例输入 #1

8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3

样例输出 #1

8

样例 #2

样例输入 #2

4 100
10 10
15 25
20 20
30 30

样例输出 #2

103

提示

【样例 #3】

见附件中的 point/point3.in 与 point/point3.ans。

第三个样例满足 k = 0。

【样例 #4】

见附件中的 point/point4.in 与 point/point4.ans。

【数据范围】

保证对于所有数据满足：1 \leq n \leq 500，0 \leq k \leq 100。对于所有给定的整点，其横纵坐标 1 \leq x_i, y_i \leq {10}^9，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

测试点编号 n \leq k \leq x_i,y_i \leq
1 \sim 2 10 0 10
3 \sim 4 10 100 100
5 \sim 7 500 0 100
8 \sim 10 500 0 {10}^9
11 \sim 15 500 100 100
16 \sim 20 500 100 {10}^9

思路：

开始看到这道题以后，就感觉和LIS有点相似，然后关注了一下数据规模，发现数据规模比较小，开始操作。

题目大意：在已知 n 个点的情况下，

还是先把代码放过来了，突然开会暂停~：

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node{
    int x,y;
} a[505];
int dp[505][105];   //dp[i][j] 表示在以第i个点为结尾，添加j个点的序列的最大长度 
int dis(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 if(a.y!=b.y){
        return a.y<b.y;
    }
}

int main(){
    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;
    /*
        现在有两个点i p 他们之间的距离如果是 j的话，需要添加 j-1个点 
    */
    for(int i=1;i<=n;i++){      //枚举n个点  计算dp[i][k]的最大值 
        for(int j=0;j<=k;j++){          //能够添加j个点 
            dp[i][j]=j+1;           //最短也得是添加的j个点连接后形成的长度为j+1的序列
            for(int p=1;p<i;p++){   //枚举前面的点 p
                //验证一下枚举到的p点
                if(a[p].x<=a[i].x && a[p].y<=a[i].y){
                    int d=dis(a[i],a[p])-1; //需要的点的个数   距离需要+1 
                    if(d<=j)    //需要添加的点的个数没有超过提供的点的个数 
                        dp[i][j]=max(dp[i][j],dp[p][j-d]+d+1);
                } 
            } 
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i][k]);
    }
    cout<<ans;
    return 0;
}