复赛4:上升点列

P8816

输入:
8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3
输出:
8

代码实现:

 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
/**************************************************************** 
 * Description: 2022 CSP-J  复赛第4题
 * Author: Alex Li
 * Date: 2023-10-05 16:32:31
 * LastEditTime: 2023-10-05 19:05:49
****************************************************************/
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

const int maxn=505;
const int maxk=105;
int n,k;

struct node{
    int x;
    int y;
}a[maxn];
//f[i][j]表示以第i点为结尾且允许添加j个点时的最长答案,枚举点i之前可以添加的所有节点。
int f[maxn][maxk]; 
//先按x比较,如果x坐标相等,按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);//从数组1下标开始,先按x,如果x相同按y
    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].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;//i和p点之间需要内个结点
                if(d<=j)f[i][j]=max(f[i][j],f[p][j-d]+d+1);//动态转移方程,把所有的p的都搜一遍,取最大值。
            }
        }
        
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,f[i][k]);
    cout<<ans;
    return 0;
}
Scroll to Top