测试点 \#5:
```
100
5436 7946
1350 3080
6245 3855
3909 5194
1257 4648
3688 5327
6101 5645
5921 1493
5758 6463
4909 1696
4405 7934
3528 4635
2079 471
1088 281
1258 7404
1610 3838
2362 5294
6553 3472
2415 7632
3596 3776
3074 4059
6481 6051
2482 705
6486 2352
2082 6662
3236 4270
854 4917
985 6312
4291 4248
4638 4670
6395 7345
7176 2863
5249 5926
5491 5346
2646 6287
4743 375
2373 5077
4748 5972
3862 6803
6494 3737
3378 6192
7388 7894
6386 3634
1759 7732
7394 5450
866 712
4294 2344
4906 7958
4789 4410
7904 4556
18 7177
5109 6407
6644 1805
544 5134
1017 2720
7285 438
7134 773
1875 3289
4042 2538
4036 3745
1845 7912
224 7018
2722 7710
4972 6329
7090 2151
5622 5291
1563 7632
1721 33
3957 4620
4532 3781
2639 6974
2420 7918
5602 6746
6485 231
6664 4155
6589 5878
5624 578
3875 6369
5721 3607
4677 2006
3298 4282
4328 4793
6035 5725
4177 2384
361 3599
1451 677
3848 6500
5606 6951
116 2837
453 369
4203 6619
4399 4659
2236 1462
5185 3076
2615 5730
908 4651
4435 2010
3787 2941
2260 5869
7163 1104
```
排序后:
```
l w 是否比前一项大
7904 4556 Yes
7394 5450 Yes
7388 7894 Yes
7285 438
7176 2863 Yes
7163 1104
7134 773
7090 2151 Yes
6664 4155 Yes
6644 1805
6589 5878 Yes
6553 3472
6494 3737 Yes
6486 2352
6485 231
6481 6051 Yes
6395 7345 Yes
6386 3634
6245 3855 Yes
6101 5645 Yes
6035 5725 Yes
5921 1493
5758 6463 Yes
5721 3607
5624 578
5622 5291 Yes
5606 6951 Yes
5602 6746
5491 5346
5436 7946 Yes
5249 5926
5185 3076
5109 6407 Yes
4972 6329
4909 1696
4906 7958 Yes
4789 4410
4748 5972 Yes
4743 375
4677 2006 Yes
4638 4670 Yes
4532 3781
4435 2010
4405 7934 Yes
4399 4659
4328 4793 Yes
4294 2344
4291 4248 Yes
4203 6619 Yes
4177 2384
4042 2538 Yes
4036 3745 Yes
3957 4620 Yes
3909 5194 Yes
3875 6369 Yes
3862 6803 Yes
3848 6500
3787 2941
3688 5327 Yes
3596 3776
3528 4635 Yes
3378 6192
3298 4282
3236 4270
3074 4059
2722 7710 Yes
2646 6287
2639 6974 Yes
2615 5730
2482 705
2420 7918 Yes
2415 7632
2373 5077
2362 5294 Yes
2260 5869 Yes
2236 1462
2082 6662 Yes
2079 471
1875 3289 Yes
1845 7912
1759 7732
1721 33
1610 3838 Yes
1563 7632 Yes
1451 677
1350 3080 Yes
1258 7404 Yes
1257 4648
1088 281
1017 2720 Yes
985 6312 Yes
908 4651
866 712
854 4917 Yes
544 5134 Yes
453 369
361 3599 Yes
224 7018 Yes
116 2837
18 7177 Yes
共计52个'YES'
```
by kexinluo @ 2022-05-04 11:57:07
但是答案(#5)是18,为什么呢?
by kexinluo @ 2022-05-04 11:58:10
@[kexinluo](/user/508834) 你可以参考一下我的代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int _x;char _c;
int read(){
_x=0;_c=getchar();
while(_c<'0'||_c>'9')_c=getchar();
while(_c<='9'&&_c>='0'){
_x=(_x<<1)+(_x<<3)+(_c^'0');
_c=getchar();
}
return(_x);
}
class thick{
public:
int l,r;
inline void input(){
l=read();
r=read();
}
inline const bool operator <(const thick& other)const{
return(l==other.l?r>other.r:l>other.l);
}
}a[5005];
int n,top;
int f[5005];
int main(){
n=read();
for(int i=1;i<=n;i++)a[i].input();
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(a[i].r>f[top])f[++top]=a[i].r;
else f[upper_bound(f+1,f+top+1,a[i].r)-f]=a[i].r;
}
printf("%d",top);
return(0);
}
```
by Etinorally @ 2022-05-04 12:05:00
应该是求 $\texttt {LIS}$
by Etinorally @ 2022-05-04 12:06:12
@[kexinluo](/user/508834) 可以按 $w $ 从大到小排序,然后求出 $l$ 的 $LIS$(最长上升子序列)的长度。
用动态规划。
by Network_Error @ 2022-07-11 16:55:52
@[kexinluo](/user/508834) 请问有答案吗,我的思路是这题应该是并查集,长和宽能兼容就视为一类,感觉思路上是对的,同样是你这个案例我感觉也是5,可是不知道为何是18
by otakuBowei @ 2022-09-08 11:31:36