「LOJ 2134」「NOI2015」小园丁与老司机

发表于

小园丁 Mr. S 负责看管一片田野，田野可以看作一个二维平面。田野上有 nn 棵许愿树，编号 1,2,3,…,n1,2,3, \ldots ,n ，每棵树可以看作平面上的一个点，其中第 ii 棵树（1≤i≤n1 \leq i \leq n）位于坐标 (xi,yi)(x_i,y_i) 。任意两棵树的坐标均不相同。

老司机 Mr. P 从原点 (0,0)(0,0) 驾车出发，进行若干轮行动。每一轮，Mr. P 首先选择任意一个满足以下条件的方向：

  • 为左、右、上、左上 45∘45^{\circ} 、右上 45∘45^{\circ} 五个方向之一。
  • 沿此方向前进可以到达一棵他尚未许愿过的树。

完成选择后，Mr. P 沿该方向直线前进，必须到达该方向上距离最近的尚未许愿的树，在树下许愿并继续下一轮行动。如果没有满足条件的方向可供选择，则停止行动。他会采取最优策略，在尽可能多的树下许愿。若最优策略不唯一，可以选择任意一种。

Constraints

n≤50000n\leq 50000 ， ∣xi∣≤109|x_i| \leq 10^9 ， 1<y≤1091<y\leq 10^9

Solution

码农题，只写了第一问……第二问是求方案，第三问上下界最小流。非常闹心，弃疗。

第一问可以用 dp 解决，具体地，将左右与其他情况分开解决。令 f(i)f(i) 表示上一步是在左边或右边的答案，g(i)g(i) 表示上一步 yy 小于当前步的答案。具体地，先按 yy 排序后按 xx 排序。然后先更新 g(i)g(i) ，直接枚举三种情况来更新即可，可以用 map 记下最近的点。对于 f(i)f(i) ，观察可得最优方案下一定会取一段前缀或一段后缀，从左向右和从右向左分别更新一遍即可。

期望得分 20 分。

Code

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<vector>
#include<map>
#define LL long long
using namespace std;
const int N=5e4+5;
const int inf=0x3f3f3f3f;
int n,x,y,w,tot,mx,ans;
int t[N],f[N],g[N];
bool ok[N][2];
vector<int> v[N];
map<int,int> ml,mm,mr;
struct node{int x,y;}o,a[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
bool cmp(int x,int y){return a[x].x<a[y].x;}
void modify()
{
	w=max(f[y],g[y]);
	g[x]=max(g[x],w+1);
	ok[x][1]=true;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		x=read();y=read();
		a[i]=(node){x,y};t[i]=y;
	}
	a[++n]=(node){0,0};sort(t+1,t+n+1);
	tot=unique(t+1,t+n+1)-t-1;
	for(int i=1;i<=n;i++)
	{
		x=lower_bound(t+1,t+tot+1,a[i].y)-t;
		v[x].push_back(i);
	}
	ml[0]=n;mm[0]=n;mr[0]=n;ok[n][0]=ok[n][1]=true;
	for(int i=2;i<=tot;i++)
	{
		int sz=v[i].size();
		sort(v[i].begin(),v[i].end(),cmp);
		for(int j=0;j<sz;j++)
		{
			x=v[i][j];o=a[x];
			if(mm.count(o.x))y=mm[o.x],modify();
			if(ml.count(o.x-o.y))y=ml[o.x-o.y],modify();
			if(mr.count(o.x+o.y))y=mr[o.x+o.y],modify();
		}
		mx=ok[v[i][0]][1]?g[v[i][0]]:-inf;
		for(int j=1;j<sz;j++)
		{
			x=v[i][j];
			if(mx!=-inf)f[x]=mx+1,ok[x][0]=true;
			if(ok[x][1])mx=max(mx+1,g[x]+j);
			else if(mx!=-inf)mx++;
		}
		mx=ok[v[i][sz-1]][1]?g[v[i][sz-1]]:-inf;
		for(int j=sz-2;j>=0;j--)
		{
			x=v[i][j];
			if(mx!=-inf)f[x]=max(f[x],mx+1),ok[x][0]=true;
			if(ok[x][1])mx=max(mx+1,g[x]+sz-1-j);
			else if(mx!=-inf)mx++;
		}
		for(int j=0;j<sz;j++)
		{
			x=v[i][j];o=a[x];
			if(ok[x][0]||ok[x][1])mm[o.x]=ml[o.x-o.y]=mr[o.x+o.y]=x;
		}
	}
	for(int i=1;i<=n;i++)ans=max(ans,max(f[i],g[i]));
	printf("%d\n",ans);
	return 0;
}