xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

struct  arr{
    
int  x,y;
}a[
1000 ];
int  n;
int  f[ 1000 ];
int  cmp( const   void *  no1, const   void *  no2){
    arr 
* nox = (arr * )no1, * noy = (arr * )no2;
    
if (nox -> x != noy -> x)  return  nox -> x - noy -> x;
    
else   return  nox -> y - noy -> y;
}
int  main()
{
    freopen(
" stick.in " , " r " ,stdin);
    freopen(
" stick.out " , " w " ,stdout);
    scanf(
" %d " , & n);
    
for ( int  i = 0 ;i < n; ++ i) 
        scanf(
" %d%d " , & a[i].x, & a[i].y);
    qsort(a,n,
sizeof (arr),cmp);
    
int  MAX = 0 ;
    
for ( int  i = 0 ;i < n; ++ i){
        f[i]
= 1 ;
        
for ( int  j = i - 1 ;j >= 0 ; -- j)
            
if (a[i].y < a[j].y && f[i] < f[j] + 1 )
                f[i]
= f[j] + 1 ;
        
if (f[i] > MAX) MAX = f[i];
    }
    printf(
" %d\n " ,MAX);
    
return   0 ;
}




posted on 2009-05-01 16:45 xfstart07 阅读(1014) 评论(2)  编辑 收藏 引用 所属分类: 代码库

FeedBack:
# re: 零件分组
2015-08-08 20:13 | most
你好!可以对这段代码做一个详细的分析吗?特别是快排结束后的那个for循环怎么理解呢?  回复  更多评论
  
# re: 零件分组[未登录]
2015-08-12 11:26 | Leon
@most
不好意思,这是几年前写的。我已经毕业工作了,很久没有做算法题了。
这应该是动态规划的算法吧。谢谢!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理