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\) 个点时的最长上升子序列长度，则满足:
\[f_{i,K}=max(f_{i,K},f_{j,K-t}+t+1)
\]
（\(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;
}