CF1662L Il Derby della Madonnina

发表于 分类于 本文字数： 1.6k 阅读时长 ≈ 2 分钟

题目描述

有 个点，第 个点在 时出现在 位置然后消失。你第 秒时在位置 ，速度为 ，问最多能赶上多少个点出现。

思路

设 表示到了第 个点，且能赶上点 的时候，最多能赶上多少点，

则 。

当 有 ，所以 ，

可以把限制条件看作点 与点 两点的切比雪夫距离为其横坐标的距离，且 在 右侧。画出来图像这样，蓝色区域是 点的限制区域。

1

我们发现， 点的范围是个边缘与坐标轴夹 的半平面交，这个边缘不与坐标轴垂直很烦，所以我们将坐标系顺时针旋转 。

2

原坐标系 对应新坐标系 。
我们实际只在乎两点间的相对位置，将坐标轴整体扩大 后不会对限制产生影响。
现在原坐标系的点 对应新坐标系的 。

新坐标系下， 的限制变为了需在 的右上部分。

不难发现，原问题变为了求平面最长不下降链，起始点强制为 ，二维偏序即可。

代码

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
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int n,ans,cnt;
ll v,t[N],a[N],dp[N];
struct node{
	ll x,y;
	inline int operator < (const node&G) const{
		if(x^G.x) return x < G.x;
		return y < G.y;
	}
}g[N];
int main(){

	scanf("%lld%lld",&n,&v);
	for(int i=1;i<=n;++i) scanf("%lld",t+i);
	for(int i=1;i<=n;++i){
		scanf("%lld",a+i); // 求新坐标系下点的坐标
		g[i].x = v*t[i]-a[i];
		g[i].y = v*t[i]+a[i];
	}
	g[++n] = {0,0};
	sort(g+1,g+1+n); // 排序掉第一维
	for(int i=1;i<=n;++i){ // 只留下(0,0)能到达的点
		if(g[i].x>=0 && g[i].y>=0) g[++cnt] = g[i];
	}
	for(int i=1;i<=cnt;++i){ // 第二维求最长不下降子序列
		if(dp[ans]<=g[i].y) dp[++ans] = g[i].y;
		else *upper_bound(dp+1,dp+1+ans,g[i].y) = g[i].y;
	}
	printf("%d",ans-1); // 减去强制选的(0,0)
	
	return 0;
}