本来觉得这不是经典的贪心吗。。果断水一次，wa了，看了看discuss，发现貌似不好水，土土的DP了一下，复杂度很高了，又T了。。。然后想想单调队列，二分什么的。。。不好往上加，直接搞了标记数组flag，暴力从大到小，遍历寻找，然后就过了。。。这算是优化吗，瞎搞。。。
#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct node
{
int x,y;
}p[];
int dp[];
int flag[];
int cmp(node a,node b)
{
if(a.x == b.x)
return a.y < b.y;
else
return a.x < b.x;
}
int main()
{
int n,i,j,ans,maxz,top;
scanf("%d",&n);
for(i = ;i < n;i ++)
{
scanf("%d%d",&p[i].x,&p[i].y);
}
memset(flag,-,sizeof(flag));
sort(p,p+n,cmp);
ans = ;
dp[] = ;
flag[] = p[].y;
top = ;
for(i = ;i < n;i ++)
{
maxz = ;
for(j = top;j >= ;j --)
{
if(p[i].x > flag[j])
{
maxz = j;
break;
}
}
dp[i] = maxz + ;
if(flag[maxz+] == -)
{
flag[maxz+] = p[i].y;
top ++;
}
else
flag[maxz+] = min(flag[maxz+],p[i].y);
}
printf("%d\n",top);
}