gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks

最长递增子序列

#include <stdio.h>

const int MAXN = 1001 ;

int n ;
int array[MAXN] ;
int memfp[MAXN] , membp[MAXN] ;

int main()
{
    
int i , j , tmp , ans ;
    
while ( scanf("%d"&n) != EOF )
    {
        
for ( i = 0 ; i < n ; ++i )
        {
            scanf(
"%d"&array[i]) ;
            memfp[i] 
= 1 ;
            
for ( j = 0 ; j < i ; ++j )
            {
                
if ( array[i] > array[j] && memfp[j] + 1 > memfp[i] )
                {
                    memfp[i] 
= memfp[j] + 1 ;
                }
            }
        }

        
for ( i = n - 1; i >= 0--i )
        {
            membp[i] 
= 1 ;
            
for ( j = n - 1; j > i ; --j )
            {
                
if ( array[i] > array[j] && membp[j] + 1 > membp[i] )
                    membp[i] 
= membp[j] + 1 ;
            }
        }
        ans 
= 0 ;
        
for ( i = 0 ; i < n ; ++i )
        {
            tmp 
= 0 ;
            
for ( j = i + 1 ; j < n ; ++j )
            {
                
if ( array[i] >= array[j] )
                    tmp 
= (tmp > membp[j] ? tmp : membp[j]) ;

            }
            ans 
= ( memfp[i] + tmp > ans ? memfp[i] + tmp : ans ) ;
        }

        printf(
"%d\n", n - ans) ;
    }
    
return 0 ;
}
posted on 2008-10-29 23:38 阅读(391) 评论(2)  编辑 收藏 引用 所属分类: DP

评论

# re: Pku 1836--Alignment 2009-07-14 10:32 dirlt
你好,这个程序好像WA的  回复  更多评论
  

# re: Pku 1836--Alignment 2009-07-14 11:32
这个程序有个地方改了
array[]在poj 1836是要用float/double,以前改int过另一题,忘记了  回复  更多评论
  


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