```
//code by rainman
//O(2nlogn+n)
#include<bits/stdc++.h>
using namespace std;
const int MAXN =5000+10;
int d[MAXN],n;
struct data{
int l,w;
}info[MAXN];
bool cmp(data a,data b)
{
if(a.l==b.l)return a.w>b.w;
return a.l>b.l;
}
int LIS()
{
d[1]=info[1].w;
int len=1;
for(int i=2;i<=n;i++)
{
if(info[i].w>=d[len])d[++len]=info[i].w;
else
{
int j=upper_bound(d+1,d+len+1,info[i].w)-d;
d[j]=info[i].w;
}
}
return len;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) //O(n)
scanf("%d%d",&info[i].l,&info[i].w);
sort(info+1,info+1+n,cmp); //O(nlogn)
printf("%d",LIS()); //O(nlogn)
return 0;
}
```
by xiangling @ 2018-08-11 19:53:13
咦，图片挂了。。
by xiangling @ 2018-08-11 19:56:05
by xiangling @ 2018-08-11 19:58:02
修好了$qwq$
by xiangling @ 2018-08-11 19:58:43
没有人啊。。。
by xiangling @ 2018-08-11 19:59:28
我凉了。。。
by xiangling @ 2018-08-11 20:04:43
哈哈
by 蓝莲花__ @ 2018-08-13 20:22:56
额我我我我。。。要。。反驳。
by 黄柠檬11 @ 2018-09-12 21:49:16
@[rainman](/space/show?uid=55804) ~~我。。。才是。。。最弱红名~~
by 黄柠檬11 @ 2018-09-12 21:49:43
@[rainman](/space/show?uid=55804) 题意并不是lis，而是找到一个lis删除它然后再找下一个直至数组为空。
贪心地想，反正得拿到空为止，按w为关键字排序后，把能放在当前物品之后的物品贪心的拿走就好，不一定要最优的拿法。
蒟蒻上代码：
```
while(!q.empty())
{
x=q[0];q.clear();
for(int i=0;i<l;++i)
if(a[i+1].y>=x)x=a[i+1].y;
else q.push_back(a[i+1].y);
l=q.size();
for(int i=0;i<l;++i)a[i+1].y=q[i];
cnt++;
}
```
为了这道题我wa了五次了都。。。。
千万别相信题解。。。。可能题目后来改过描述了
by 田阙西 @ 2018-09-23 17:53:53