题目描述
在一个二维平面内，给定 n n n 个整数点 ( x i , y i ) (x_i, y_i) (xi,yi)，此外你还可以自由添加 k k k 个整数点。
你在自由添加 k k k 个点后，还需要从 n + k n + k n+k 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 1 1 1 而且横坐标、纵坐标值均单调不减，即 x i + 1 − x i = 1 , y i + 1 = y i x_{i+1} - x_i = 1, y_{i+1} = y_i xi+1−xi=1,yi+1=yi 或 y i + 1 − y i = 1 , x i + 1 = x i y_{i+1} - y_i = 1, x_{i+1} = x_i yi+1−yi=1,xi+1=xi。请给出满足条件的序列的最大长度。
【数据范围】
保证对于所有数据满足： 1 ≤ n ≤ 500 1 \leq n \leq 500 1≤n≤500， 0 ≤ k ≤ 100 0 \leq k \leq 100 0≤k≤100。对于所有给定的整点，其横纵坐标 1 ≤ x i , y i ≤ 10 9 1 \leq x_i, y_i \leq {10}^9 1≤xi,yi≤109，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。
思路
考虑动态规划，记 d p i , j dp_{i,j} dpi,j 表示以第 i i i 个点为结尾，已经插入 j j j 个自由点的最长长度。
首先将点对按照 x , y x,y x,y 大小排个序，确保转移时横纵坐标比当前节点小的点对都在它前面，否则无法转移。
容易发现， d p i , j = max l = 1 i − 1 d p l , j − d i s ( i , l ) + 1 + d i s ( i , l ) + 1 , ( y i ≥ y l , j − d i s ( i , l ) + 1 ≥ 0 ) dp_{i,j} = \max_{l=1}^{i - 1}{dp_{l,j -dis(i,l)+1} + dis(i,l)+1},(y_i \geq y_l,j -dis(i,l)+1 \geq 0) dpi,j=maxl=1i−1dpl,j−dis(i,l)+1+dis(i,l)+1,(yi≥yl,j−dis(i,l)+1≥0), d p i , j dp_{i,j} dpi,j 初始值赋值为 j + 1 j+1 j+1（全部用在它前面）。
解释：因为两个点中间因插入的点对数量等于它们欧几里得距离减去一（因为头尾都已经有了），文中 d i s ( i , l ) dis(i,l) dis(i,l) 表示的就是两者的欧几里得距离剪去 1 1 1。计算方式如下：
int dis(int a,int b) {
return abs(edge[a].x - edge[b].x) + abs(edge[a].y - edge[b].y) - 1;
}
最后输出的答案就是
a
n
s
ans
ans 就是
d
p
i
,
j
+
(
k
−
j
)
dp_{i,j} + (k - j)
dpi,j+(k−j) 的最大值（加上
k
−
j
k-j
k−j 代表剩下所有没用完的直接加在该点后面）
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
struct node{
int x,y;
friend bool operator <(node a,node b) {
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
}edge[505];
int dp[505][105],ans = -1e18;
int dis(int a,int b) {
return abs(edge[a].x - edge[b].x) + abs(edge[a].y - edge[b].y) - 1;
}
signed main() {
scanf("%lld %lld",&n,&k);
for(int i = 1;i <= n;i++) scanf("%lld%lld",&edge[i].x,&edge[i].y);
sort(edge + 1,edge + n + 1);
for(int i = 1;i <= n;i++) {
for(int j = 0;j <= k;j++) {
dp[i][j] = j + 1;
for(int l = 1;l < i;l++) {
int d = dis(i,l);
if(edge[l].y <= edge[i].y and d <= j) {
dp[i][j] = max(dp[i][j],dp[l][j - d] + d + 1);
}
}
ans = max(ans,dp[i][j] + k - j);
}
}
printf("%lld\n",ans);
return 0;
}