#include  < stdio.h >
#include 
< stdlib.h >
#include 
< string .h >

int   const  inf =   1 << 29 ;
int  n;
struct  Point {
    
int  Lx, Ly, Rx, Ry;
}
;

Point pnt[
16 ];
int   need[ 16 ], dp[ 1 << 15 ][ 15 ], color[ 16 ];

void  init() {
    
for int  i =   0 ; i <=  n;  ++ i ) need[i] =   0 ;
    
    
for int  i =   0 ; i <  n;  ++ i ) {
        
for ( int  j =   0 ; j <  n;  ++ j ) {
            
if ( i ==  j )  continue ;

            
if ( pnt[j].Ry <=  pnt[i].Ly  &&  pnt[j].Lx <  pnt[i].Rx ) {
                need[i]
|=  ( 1 << j);
            }

        }

    }

}


void  solve() {
    
for int  i =   0 ; i <  ( 1 << n);  ++ i )
        
for ( int  j =   0 ; j <  n;  ++ j ) dp[i][j] =  inf;

    dp[
0 ][ 0 ] =   0 ;
    
for int  i =   0 ; i <  n;  ++ i )
        
if ( need[i] ==   0  ) dp[ 1 << i][i] =   1 ;
    
    
for int  s =   0 ; s <  ( 1 << n);  ++ s ) {
        
for int  i =   0 ; i <  n;  ++ i ) {
            
if ( ( s &  ( 1 << i) ) ==   0  )  continue ;

            
for int  j =   0 ; j <  n;  ++ j ) {
                
if ( s &  ( 1 << j) )  continue ;
                
if ( (s &  need[j]) !=  need[j] )  continue ;

                
if ( dp[s][i] +  ( color[i] !=  color[j] ) <  dp[s | ( 1 << j)][j] ) {
                    dp[s
| ( 1 << j)][j] =  dp[s][i] +  ( color[i] !=  color[j] );
                }

            }

        }

    }


    
int  ans =  inf;
    
for int  i =   0 ; i <  n;  ++ i )
        
if ( dp[( 1 << n) - 1 ][i] <  ans ) ans =  dp[( 1 << n) - 1 ][i];

    printf(
" %d\n " , ans );
}


int  main() {
    
int  test;
    scanf(
" %d " , & test );

    
while ( test --  ) {
        scanf(
" %d " , & n );

        
for int  i =   0 ; i <  n;  ++ i ) {
            scanf(
" %d%d%d%d " & pnt[i].Ly,  & pnt[i].Lx,  & pnt[i].Ry,   & pnt[i].Rx );
            scanf(
" %d " , color +  i );
        }


        init();
        solve();
    }

    
    
return   0 ;
}

posted on 2009-10-08 14:54 Darren 阅读(501) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理