本来觉得这不是经典的贪心吗。。果断水一次，wa了，看了看discuss，发现貌似不好水，土土的DP了一下，复杂度很高了，又T了。。。然后想想单调队列，二分什么的。。。不好往上加，直接搞了标记数组flag，暴力从大到小，遍历寻找，然后就过了。。。这算是优化吗，瞎搞。。。
1
#include <cstring>
2
#include <cstdio>
3
#include <
string
>
4
#include <iostream>
5
#include <algorithm>
6
#include <cmath>
7
using
namespace
std;
8
struct
node
9
{
10
int
x,y;
11
}p[
100001
];
12
int
dp[
100001
];
13
int
flag[
100001
];
14
int
cmp(node a,node b)
15
{
16
if
(a.x ==
b.x)
17
return
a.y <
b.y;
18
else
19
return
a.x <
b.x;
20
}
21
int
main()
22
{
23
int
n,i,j,ans,maxz,top;
24
scanf(
"
%d
"
,&
n);
25
for
(i =
0
;i < n;i ++
)
26
{
27
scanf(
"
%d%d
"
,&p[i].x,&
p[i].y);
28
}
29
memset(flag,-
1
,
sizeof
(flag));
30
sort(p,p+
n,cmp);
31
ans =
1
;
32
dp[
0
] =
1
;
33
flag[
1
] = p[
0
].y;
34
top =
1
;
35
for
(i =
1
;i < n;i ++
)
36
{
37
maxz =
0
;
38
for
(j = top;j >=
1
;j --
)
39
{
40
if
(p[i].x >
flag[j])
41
{
42
maxz =
j;
43
break
;
44
}
45
}
46
dp[i] = maxz +
1
;
47
if
(flag[maxz+
1
] == -
1
)
48
{
49
flag[maxz+
1
] =
p[i].y;
50
top ++
;
51
}
52
else
53
flag[maxz+
1
] = min(flag[maxz+
1
],p[i].y);
54
}
55
printf(
"
%d\n
"
,top);
56
}
