xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

struct  arr{
    
int  x,y,c;
}a[
501 ];
int  N;
int  f[ 501 ];
int  p[ 501 ];
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;
}
int  main()
{
    scanf(
" %d " , & N);
    
for ( int  i = 0 ;i < N; ++ i){
        scanf(
" %d%d " , & a[i].x, & a[i].y);
        a[i].c
= i + 1 ;
    }
    qsort(a,N,
sizeof (arr),cmp);
    
int  Max = 0 ,pre;
    
for ( int  i = 0 ;i < N; ++ i){
        f[i]
= 1 ; p[i] = i;
        
for ( int  j = 0 ;j < i; ++ j)
            
if (a[i].x > a[j].x && a[j].y > a[i].y)
                
if (f[i] < f[j] + 1 ){
                    f[i]
= f[j] + 1 ;
                    p[i]
= j;
                }
        
if (f[i] > Max){
            Max
= f[i];
            pre
= i;
        }
        
else   if (f[i] == Max)
            
if (a[p[i]].c < a[pre].c)
                pre
= i;
    }
    printf(
" %d\n " ,Max);
    
while (pre != p[pre]){
        printf(
" %d  " ,a[pre].c);
        pre
= p[pre];
    }
    printf(
" %d\n " ,a[pre].c);
    
return   0 ;
}




posted on 2009-05-31 00:06 xfstart07 阅读(164) 评论(0)  编辑 收藏 引用 所属分类: 代码库

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