【BZOJ】2924: [Poi1998]Flat broken lines

题意

平面上有\(n\)个点，如果两个点的线段与\(x\)轴的角在\([-45^{\circ}, 45^{\circ}]\)，则两个点可以连线。求最少的折线(折线由线段首尾相连)使得覆盖所有点。

分析

bzoj的题面有坑，不是15而是45。

将点绕原点旋转\(-45^{\circ}\)后，能连线的话就是另一个点在左上角。那么问题就是求最少链个数。根据定理，最少链个数=最大反链长度。

题解

用bit求最大反链即可。

#include <bits/stdc++.h>

using namespace std;

inline int getint() {

	int x=0, f=1, c=getchar();

	for(; c<48||c>57; f=c=='-'?-1:f, c=getchar());

	for(; c>47&&c<58; x=x*10+c-48, c=getchar());

	return x*f;

}

const int N=30005;

struct ip {

	int x, y;

	void scan() {

		int a=getint(), b=getint();

		x=a-b, y=-(a+b);

	}

}p[N];

inline bool cmpy(const ip &a, const ip &b) {

	return a.y<b.y;

}

inline bool cmpx(const ip &a, const ip &b) {

	return a.x==b.x?a.y>b.y:a.x<b.x;

}

int tot, n, s[N];

inline void upd(int x, int g) {

	for(; x<=tot; x+=x&-x) {

		s[x]=max(s[x], g);

	}

}

inline int sum(int x) {

	int y=0;

	for(; x; x-=x&-x) {

		y=max(y, s[x]);

	}

	return y;

}

int main() {

	n=getint();

	for(int i=1; i<=n; ++i) {

		p[i].scan();

	}

	sort(p+1, p+1+n, cmpy);

	for(int i=1, now=-100001; i<=n; ++i) {

		p[i].y==now?(p[i].y=tot):(now=p[i].y, p[i].y=++tot);

	}

	sort(p+1, p+1+n, cmpx);

	int ans=0;

	for(int i=1; i<=n; ++i) {

		int d=sum(p[i].y-1)+1;

		upd(p[i].y, d);

		ans=max(ans, d);

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

【BZOJ】2924: [Poi1998]Flat broken lines

题意

分析

题解

最新文章

热门文章