@[冰冻罗非鱼](/user/225941)
如果您打算使用LIS来解题,您能具体描述一下您的思路吗?
by metaphysis @ 2020-04-11 12:41:21
@[metaphysis](/user/333388)
即是否可以保证为最优解。
by metaphysis @ 2020-04-11 12:41:54
@[冰冻罗非鱼](/user/225941) 双降排序贪心即可
by twelveZ @ 2020-04-11 12:53:11
@[metaphysis](/user/333388) 就是先把长全部排一遍序,然后再搜一个最长序列
by 冰冻罗非鱼 @ 2020-04-13 10:04:14
@[code_universe](/user/107232) 不会啊
大佬教一下
by 冰冻罗非鱼 @ 2020-04-13 10:04:33
@[冰冻罗非鱼](/user/225941)
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct note{
int l,w;
}a[5005];
bool use[5005];
bool cmp(note x,note y){
if(x.l==y.l) return x.w>y.w;
else return x.l>y.l;
}
int ans=0,tot=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].l>>a[i].w;
sort(a+1,a+n+1,cmp);
while(tot<n){
int st;
for(st=1;use[st];st++);
int L=a[st].l,W=a[st].w;
ans++;tot++;use[st]=1;
for(int i=st+1;i<=n;i++)
if(a[i].l<=L&&a[i].w<=W&&use[i]==0){
use[i]=1;tot++;L=a[i].l;W=a[i].w;
// cout<<a[i].l<<" "<<a[i].w<<endl;
}
// cout<<endl;
}
cout<<ans<<endl;
}
```
by twelveZ @ 2020-04-13 10:32:41
我觉得应该是排一下长度然后求最长不增序列的个数吧,类似导弹拦截那个QAQ
by cybercsc @ 2020-08-07 18:21:56