复赛4：上升点列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

/**************************************************************** 
 * Description: 2022 CSP-J  复赛第4题 上升点列
 * Author: Alex Li
 * Date: 2023-10-05 16:32:31
 * LastEditTime: 2024-10-18 10:38:15
****************************************************************/
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

const int maxn=505; // 最大的整点数
const int maxk=105; // 最大的可自由添加的整点数
int n, k; // n表示给定的整点数，k表示可添加的整点数

// 定义一个结构体node，用来表示二维平面上的点
struct node {
    int x; // 点的横坐标
    int y; // 点的纵坐标
} a[maxn]; // 用来存储所有的点，包括输入的n个点

// f[i][j] 表示以第i个点为序列的结尾，且允许添加j个点时，所能构成的最长序列长度
int f[maxn][maxk]; 

// 自定义的比较函数，按照x坐标排序，若x坐标相同则按y坐标排序
bool cmp(node a, node b) {
    if (a.x != b.x) return a.x < b.x; // 按x坐标升序排序
    else return a.y < b.y; // 若x相同，按y坐标升序排序
}

int main() {
    // 输入点的数量n和可添加的点的数量k
    cin >> n >> k;
    
    // 输入每个点的坐标
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    
    // 对点进行排序，先按x，再按y
    sort(a + 1, a + n + 1, cmp);
    
    // 动态规划部分
    for (int i = 1; i <= n; i++) { // 遍历每一个点
        for (int j = 0; j <= k; j++) { // 遍历每一个可能添加的点数
            f[i][j] = j + 1; // 初始值为当前可以添加的点数加1（自身点）
            
            // 对于每一个前面的点p，尝试从点p转移到点i
            for (int p = 1; p < i; p++) {
                // 判断点p是否可以与点i相连，要求点p的横纵坐标都小于等于点i
                if (a[p].x <= a[i].x && a[p].y <= a[i].y) {
                    int d = a[i].x - a[p].x + a[i].y - a[p].y - 1; // 计算p和i之间需要填充的点数d
                    
                    // 如果所需添加的点数d不超过允许的点数j，则进行状态转移
                    if (d <= j) 
                        f[i][j] = max(f[i][j], f[p][j - d] + d + 1); // 动态转移方程，计算最大值
                }
            }
        }
    }
    
    // 计算最大值，遍历所有以i为结尾的序列，取最大值
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, f[i][k]);
    
    // 输出最终结果
    cout << ans;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/**************************************************************** 
 * Description: 2022 CSP-J  复赛第4题  pair结构
 * Author: Alex Li
 * Date: 2023-10-05 16:32:31
 * LastEditTime: 2024-10-19 17:17:54
****************************************************************/
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn=505;
const int maxk=105;
int n,k;
pair<int,int> a[maxn]; //表示平面上每个点，有两坐标
int f[maxn][maxk]; //f[i][j]表示以第i点为结尾且允许添加j个点时的最长答案，枚举点i之前可以添加的所有节点。

int main(){
    cin>>n>>k;
    for (int i = 1; i <=n; i++)cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1);//从数组1下标开始
    for (int i = 1; i <=n; i++){
        for (int j = 0; j <=k; j++){
            f[i][j]=j+1;
            for (int p = 1; p <i; p++)
            if(a[p].first<=a[i].first&&a[p].second<=a[i].second){
                int d=a[i].first-a[p].first+a[i].second-a[p].second-1;
                if(d<=j)f[i][j]=max(f[i][j],f[p][j-d]+d+1);
              
            }
        }
        
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,f[i][k]);
    cout<<ans;
    return 0;
}