最长上升子序列-dp打法
陈子骏
2018-04-01 16:53:07
```
#include<bits/stdc++.h>
using namespace std;
int dp[200001];
int n;
int ans;
struct edg{
int a,b;
}w[200001];
int cmp(edg x,edg y)
{
return x.a<y.a;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i].a,&w[i].b);
}
for(int i=1;i<=n;i++)dp[i]=1;
sort(w+1,w+n+1,cmp);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(w[j].b>w[i].b)dp[j]=max(dp[j],dp[i]+1);
}
ans=max(dp[i],ans);
}
printf("%d",ans);
return 0;
}
```