【题解】CF1408D Searchlights

CF1408D Searchlights

\(\text{Solution:}\)

经典模型(?) 来巩固一下

考虑移动的方案,必然是向上移动到某个等塔同一水平后再向右走。

那么,如果我们可以知道,在移动 \(x\) 步的情况下,所有海盗向右走的最短距离,那是不是就很好做了?

先考虑如何处理这个东西。枚举海盗和灯塔,那么 \(f_{|y-y_i|}=\max\{f,|x-x_i|\}\)

这是因为枚举了所有海盗在某一水平线的平移距离,直接取最大值即可。

那如何计算答案?考虑如果我们要移动 \(x\) 步往上走,那么我向右移动的距离必然要是移动 \(x\) 步以上的往右距离的最大值。

因为如果不移动这么多步,那一定可以被右上方一个点给全部遮住。

所以我们就可以直接倒序枚举记录最大值更新了。

注意到我们取了后缀最大值,所以有些点是不必要被 \(dp\) 到的。不行也可以直接在初始化的时候赋值为最小值即可。

枚举的时候,我们发现,枚举 \(n,m\) 是不可省的,但是能不能不枚举步数?因为最优的步数一定是跳跃到某个灯塔等高,所以可以直接去掉枚举高度的一维,这样就 \(O(nm)\) 了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int INF=1e6+10;
int n,m;
struct pt{
	int u,v;
}q[N],t[N];
int f[INF];
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
int vis[INF];
int main(){
	freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d%d",&q[i].u,&q[i].v);
	for(int i=1;i<=m;++i)scanf("%d%d",&t[i].u,&t[i].v);
	int mx=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(q[i].v>t[j].v)continue;
			int c=t[j].v-q[i].v;
			mx=Max(mx,c);
			f[c]=Max(f[c],Max(0,t[j].u-q[i].u+1));
		}
	}
	int ans=mx+1;
	int Mx=-1;
	for(int i=mx;~i;--i){
		Mx=Max(Mx,f[i]);
		ans=Min(ans,Mx+i);
	}
	printf("%d\n",ans);
	return 0;
}
上一篇:动态规划第一节课


下一篇:洛谷 P6776 - [NOI2020] 超现实树(找性质,神仙题)