[刷题笔记] CSP-J 2022 T4 上升点列

Description

在一个二维平面内，给定 \(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\)。请给出满足条件的序列的最大长度。

评测地址：https://www.luogu.com.cn/problem/P8816

Analysis

先考虑最简单的情况，当 \(k=0\) 时，我们只在题目已知的点中选，这就是一个 最长上升子序列问题。处理到这里可以获得 40 pts 的好成绩。

对于可以添加点的情况，解题的大方向还是 最长上升子序列模型。对于 \(\forall a_i,a_j\)，不妨枚举在他们中间添加点的个数。设 \((x_1,y_1),(x_2,y_2)\) 表示当前处理的点，若合法，我们显然至少需要添加 \(x_2-x_1+y_2-y_1\) 个点才能符合题意（这里合法指单调上升。）

形式化地，设 \(f_{i,K}\) 表示前 \(i\) 位，已经添加了 \(K\) 个点时的最长上升子序列长度，则满足:

（\(t=(x_2-x_1+y_2-y_1)\)）

至于预处理，初始化使得 \(f_{i,K}=K+1\)（别忘了加上本身）

分析完毕，代码如下：

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define x first 
#define y second
using namespace std;
const int N = 10010;
typedef pair<int,int> PAIR; 
int n,k;
PAIR a[N];
int f[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1);

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            f[i][j] = j+1;
        }
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=i-1;j>=1;j--)
        {
            if(a[j].y > a[i].y) continue; //不满足单调上升
            int dist = a[i].x - a[j].x + a[i].y-a[j].y-1;
            for(int p = dist;p <= k;p ++)
            {
                f[i][p] = max(f[i][p],f[j][p-dist]+dist+1); //枚举添加点的数量
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++) ans = max(ans,f[i][k]);
    cout<<ans<<endl;
    return 0;
}