POI2013 Laser

POI
dp

POI2013 Laser

题目大意：

给出n条线段。在(0,0)处引出k条射线，每一条线段最多被一条射线穿过，问最多一共可以穿过几条线段。

$PS.$ 算是蛮简单的一道题。

题解：

把一个点反映成此点的斜率，那么穿过某线段的射线可反映为一个区间。

于是定义dp[i][j]表示引出i条射线后，在斜率为j处，发现了一条射线的最大价值。

用滚动数组滚掉一维，题目即可得解。

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
} 
const int N=500001,inf=(int)1e9;
int k,n,tot;
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
struct Fr{
	int son,mom;
	bool operator < (const Fr &tmp)const{
		return 1LL*son*tmp.mom<1LL*mom*tmp.son;	
	}
	bool operator ==(const Fr &tmp)const{
		if(son==tmp.son&&mom==tmp.mom)return true;
		return false;
	}
}tmp[N<<1];
struct node{
	Fr L,R;
}num[N];
struct Segment{
	int L,R;
}A[N];
int dp[2][N<<1],mi[N<<1],sum[N<<1];
struct Segment_Tree{
	struct node{
		int L,R,mi,flag;
	}tree[N<<3];
	void up(int p){
		tree[p].mi=min(tree[p<<1].mi,tree[p<<1|1].mi);
	}
	void down(int p){
		if(tree[p].flag!=inf){
			tree[p<<1].mi=min(tree[p<<1].mi,tree[p].flag);
			tree[p<<1|1].mi=min(tree[p<<1|1].mi,tree[p].flag);
			tree[p<<1].flag=min(tree[p<<1].flag,tree[p].flag);
			tree[p<<1|1].flag=min(tree[p<<1|1].flag,tree[p].flag);
			tree[p].flag=inf;
		}
	}
	void build(int L,int R,int p){
		tree[p].L=L,tree[p].R=R,tree[p].flag=inf;
		if(L==R){
			tree[p].mi=L;
			return;
		}
		int mid=L+R>>1;
		build(L,mid,p<<1);
		build(mid+1,R,p<<1|1);
		up(p);
	}
	void update(int L,int R,int x,int p){
		if(tree[p].L==L&&tree[p].R==R){
			tree[p].mi=min(tree[p].mi,x);
			tree[p].flag=min(tree[p].flag,x);
			return;
		}
		down(p);
		int mid=tree[p].L+tree[p].R>>1;
		if(R<=mid)update(L,R,x,p<<1);
		else if(L>mid)update(L,R,x,p<<1|1);
		else update(L,mid,x,p<<1),update(mid+1,R,x,p<<1|1);
		up(p);
	}
	int query(int x,int p){
		if(tree[p].L==tree[p].R)return tree[p].mi;
		down(p);
		int mid=tree[p].L+tree[p].R>>1;
		if(x<=mid)return query(x,p<<1);
		return query(x,p<<1|1);
	}
}T;
int main(){
	Rd(k),Rd(n);
	for(int i=1,a,b,c,d,div;i<=n;i++){
		Rd(a),Rd(b),Rd(c),Rd(d);
		div=gcd(a,b);
		a/=div,b/=div;
		div=gcd(c,d);
		c/=div,d/=div;
		tmp[++tot]=(Fr){b,a};
		num[i].L=tmp[tot];
		tmp[++tot]=(Fr){d,c};
		num[i].R=tmp[tot];
	}
	sort(tmp+1,tmp+1+tot);
	tot=unique(tmp+1,tmp+1+tot)-tmp-1;
	T.build(1,tot,1);
	for(int i=1;i<=n;i++){
		A[i].L=lower_bound(tmp+1,tmp+1+tot,num[i].L)-tmp;
		A[i].R=lower_bound(tmp+1,tmp+1+tot,num[i].R)-tmp;
		if(A[i].L>A[i].R)swap(A[i].L,A[i].R);
		sum[A[i].L]++;
		sum[A[i].R+1]--;
		T.update(A[i].L,A[i].R,A[i].L,1);
	}
	for(int i=1;i<=tot;i++){
		sum[i]+=sum[i-1];
		mi[i]=T.query(i,1);
	}
	bool cur=0;
	for(int j=1;j<=k;j++){
		cur^=1;
		memset(dp[cur],0,sizeof(dp[cur]));
		for(int i=1;i<=tot;i++)
			dp[cur][i]=max(dp[cur^1][mi[i]-1]+sum[i],dp[cur][i-1]);
	}
	cout<<dp[cur][tot]<<endl;
	return 0;
}
分享到 评论