> 做题之前听说是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;
>    }
你更水，还o(n).....怪雷人的
> };
> 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;
> }

• Re:这道题还听有人说是dp，原来一道超级水题。 (20) wyylling 2009-12-17 12:04:59
  • Re:这道题还听有人说是dp，原来一道超级水题。 (48) ccsu2008021220 2010-06-01 12:56:24