xfstart07
Get busy living or get busy dying

#include < cstdio >
#include
< cstring >
using   namespace  std;

int  N;
int  a[ 30010 ];
int  f[ 30010 ][ 4 ];
inline 
int  min( int  x, int  y)
return  x > y ? y:x; }
int  main()
{
    scanf(
" %d " , & N);
    
for ( int  i = 1 ;i <= N; ++ i)
        scanf(
" %d " , & a[i]);
    
for ( int  i = 1 ;i <= 3 ; ++ i)
        f[
0 ][i] = f[N + 1 ][i] = 0 ;
    
for ( int  i = 1 ;i <= N; ++ i)
        
if (a[i] == 1 ){
            f[i][
1 ] = f[i - 1 ][ 1 ];
            f[i][
2 ] = min(f[i - 1 ][ 1 ],f[i - 1 ][ 2 ] + 1 );
            f[i][
3 ] = min(min(f[i - 1 ][ 1 ],f[i - 1 ][ 2 ] + 1 ),f[i - 1 ][ 3 ] + 1 );
        }
        
else   if (a[i] == 2 ){
            f[i][
1 ] = f[i - 1 ][ 1 ] + 1 ;
            f[i][
2 ] = min(f[i - 1 ][ 1 ] + 1 ,f[i - 1 ][ 2 ]);
            f[i][
3 ] = min(min(f[i - 1 ][ 1 ] + 1 ,f[i - 1 ][ 2 ]),f[i - 1 ][ 3 ] + 1 );
        }
        
else {
            f[i][
1 ] = f[i - 1 ][ 1 ] + 1 ;
            f[i][
2 ] = min(f[i - 1 ][ 1 ] + 1 ,f[i - 1 ][ 2 ] + 1 );
            f[i][
3 ] = min(min(f[i - 1 ][ 1 ] + 1 ,f[i - 1 ][ 2 ] + 1 ),f[i - 1 ][ 3 ]);
        }
    
int  Min = 0xFFFFFFF ;
    
for ( int  i = 1 ;i <= 3 ; ++ i)
        
if (f[N][i] < Min) Min = f[N][i];
    
for ( int  i = N;i >= 1 ; -- i)
        
if (a[i] == 1 ){
            f[i][
1 ] = f[i + 1 ][ 1 ];
            f[i][
2 ] = min(f[i + 1 ][ 1 ],f[i + 1 ][ 2 ] + 1 );
            f[i][
3 ] = min(min(f[i + 1 ][ 1 ],f[i + 1 ][ 2 ] + 1 ),f[i + 1 ][ 3 ] + 1 );
        }
        
else   if (a[i] == 2 ){
            f[i][
1 ] = f[i + 1 ][ 1 ] + 1 ;
            f[i][
2 ] = min(f[i + 1 ][ 1 ] + 1 ,f[i + 1 ][ 2 ]);
            f[i][
3 ] = min(min(f[i + 1 ][ 1 ] + 1 ,f[i + 1 ][ 2 ]),f[i + 1 ][ 3 ] + 1 );
        }
        
else {
            f[i][
1 ] = f[i + 1 ][ 1 ] + 1 ;
            f[i][
2 ] = min(f[i + 1 ][ 1 ] + 1 ,f[i + 1 ][ 2 ] + 1 );
            f[i][
3 ] = min(min(f[i + 1 ][ 1 ] + 1 ,f[i + 1 ][ 2 ] + 1 ),f[i + 1 ][ 3 ]);
        }
    
for ( int  i = 1 ;i <= 3 ; ++ i)
        
if (f[ 1 ][i] < Min) Min = f[ 1 ][i];
    printf(
" %d\n " ,Min);
    
return   0 ;
}

#include < cstdio >
#include
< cstring >
using   namespace  std;

int  N;
int  a[ 30010 ];
int  f[ 30010 ][ 4 ];
int  main()
{
    scanf(
" %d " , & N);
    
for ( int  i = 1 ;i <= N; ++ i)
        scanf(
" %d " , & a[i]);
    
for ( int  i = 1 ;i <= 3 ; ++ i)
        f[
0 ][i] = f[N + 1 ][i] = 0 ;
    
for ( int  i = 1 ;i <= N; ++ i){
        
for ( int  j = 1 ;j <= 3 ; ++ j)
            f[i][j]
= 0xFFFFFFF ;
        
for ( int  j = 1 ;j <= 3 ; ++ j)
            
for ( int  k = 1 ;k <= j; ++ k)
                
if (f[i][j] > f[i - 1 ][k] + (a[i] != j))
                    f[i][j]
= f[i - 1 ][k] + (a[i] != j);
    }
    
int  Min = 0xFFFFFFF ;
    
for ( int  i = 1 ;i <= 3 ; ++ i)
        
if (f[N][i] < Min) Min = f[N][i];
    
for ( int  i = N;i >= 1 ; -- i){
        
for ( int  j = 1 ;j <= 3 ; ++ j)
            f[i][j]
= 0xFFFFFFF ;
        
for ( int  j = 1 ;j <= 3 ; ++ j)
            
for ( int  k = 1 ;k <= j; ++ k)
                
if (f[i][j] > f[i + 1 ][k] + (a[i] != j))
                    f[i][j]
= f[i + 1 ][k] + (a[i] != j);
    }
    
for ( int  i = 1 ;i <= 3 ; ++ i)
        
if (f[ 1 ][i] < Min) Min = f[ 1 ][i];
    printf(
" %d\n " ,Min);
    
return   0 ;
}




posted on 2009-08-10 17:15 xfstart07 阅读(116) 评论(0)  编辑 收藏 引用

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