最長遞增子序列
#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 ;
}