本來覺得這不是經典的貪心嗎。。果斷水一次，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
}
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
