和最长非上升子序列一个思想：
中间找到大的就替换掉（1，没有多花时间。2，大替小过后可以更延伸的更长。）末尾就代表没找到，则新加一段子序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005;
int dp[maxn];
struct Node
{
int l,w;
}node[maxn];
int cmp(const Node a,const Node b)
{
if(a.l!=b.l)
return a.l>b.l;
else
return a.w>b.w;
}
int main()
{
int n;
int k=1;
cin>>n;
for(int i=1;i<=n;i++)
cin>>node[i].l>>node[i].w;
sort(node+1,node+1+n,cmp);
dp[1]=node[1].w;
for(int i=2;i<=n;i++)
{
int j=lower_bound(dp+1,dp+1+k,node[i].w)-dp;
if(j<=k) dp[j]=node[i].w;
else dp[++k]=node[i].w;
}
cout<<k<<endl;
}
|
近期评论