做题之前听说是dp，怀着dp的心情去解，后来越来越发现不对劲，值感觉这道题没学算法也能AC掉，就是一个简单的排序在加选取策略就a了，复杂度也就O(n).
贴代码：
#include<iostream>
#include<algorithm>
using namespace std;
struct lct{
    int x,y;
}a[50001];
struct pt_cmp
{
   bool operator()(const lct &a,const lct &b)const 
   {
      if ( a.x == b.x ) return a.y < b.y;
      return a.x < b.x;
   }
};
int main()
{
    int n;
    while(cin>>n&&n)
    {
        for(int i=1;i<=n;i++)
           cin>>a[i].x>>a[i].y;
        sort(a+1,a+n+1,pt_cmp());
        int l=a[n].x,c=a[n].y;
        int ans=1;
        for(int j=n-1;j>=1;j--)
        {
            if(a[j].x==l) continue;
            else
                if(a[j].y>c)
                {
                    c=a[j].y;
                    l=a[j].x;
                    ans++;
                }
        }
        cout<<ans<<endl;        
    }
    return 0;
}

• 都排序了，还O(n)……o(╯□╰)o (955) jyd 2009-10-07 09:44:37
• Re:排序最快是nlogn吧？？？ (957) Nevam 2009-12-10 20:03:50
• Re:这道题还听有人说是dp，原来一道超级水题。 (977) wyylling 2009-12-17 12:04:37
  • Re:这道题还听有人说是dp，原来一道超级水题。 (20) wyylling 2009-12-17 12:04:59
    • Re:这道题还听有人说是dp，原来一道超级水题。 (48) ccsu2008021220 2010-06-01 12:56:24