当前位置: 代码迷 >> 综合 >> pku 1632 Vase Collection
  详细解决方案

pku 1632 Vase Collection

热度:81   发布时间:2023-12-21 05:13:37.0

这道题用了状态压缩。

状态压缩常常用在DP中,而这道题是搜索做的,有些意思。

这道题其实可以看作在一个大矩阵中找一个最大的小正方形阵,二维需要加一重搜索,如果像http://acm.pku.edu.cn/JudgeOnline/problem?id=2441 Arrange the bulls一样,就不用再搜了。

 

#include  < iostream >
#define  M 37
using   namespace  std;

int  table[M][M] = { 0 },n;
long   long  state[M] = { 0 };
int  bitcnt[ 0x11ffff + 1 ] = { 0 };

int  calbit( long   long  s)
{
    
return  bitcnt[s & 0x11ffff ] + bitcnt[s >> 18 ];
}
bool  dfs( int  i, int  l, long   long  s, int  len)
{
    
while  (i <= 36 && state[i] == 0 )
        
++ i;
    
if  (i > 36 && l > 0 ) return   false ;
    
if  (l == 0 )
    {
        
return  calbit(s) != 36 && calbit(s) >= len;
    }
    
if  (calbit(s) < len) return   false ;
    
return  dfs(i + 1 ,l,s,len) || dfs(i + 1 ,l - 1 ,s & state[i],len);
}

int  main()
{
    
int  nCase,i,s,t,j;
    
for  (i = 1 ;i <= 0x11ffff ;i ++ )
    {
        
int  cnt = 0 ;
        j
= i;
        
while  (j)
        {
            
if  ((j & 0x01 ) == 1 ) ++ cnt;
            j
>>= 1 ;
        }
        bitcnt[i]
= cnt;
    }
    cin
>> nCase;
    
while  (nCase -- )
    {
        cin
>> n;
        memset(table,
0 , sizeof (table));
        memset(state,
0 , sizeof (state));
        state[
0 ] = (1LL << 36 ) - 1 ;
        
for  (i = 0 ;i < n;i ++ )
        {
            cin
>> s >> t;
            table[s][t]
= 1 ;
        }
        
for  (i = 1 ;i <= 36 ;i ++ )
        {
            
for  (j = 1 ;j <= 36 ;j ++ )
            {
                state[i]
<<= 1 ;
                
if  (table[i][j] == 1 ) state[i] |= 0x01 ;
            }
        }
        
for  (j = 2 ;j <= n;j ++ )
        {
            
if  (dfs( 1 ,j,state[ 0 ],j) == false )
                
break ;
        }
        cout
<< j - 1 << endl;
    }
}

 

关于状态压缩DP的题目,http://acm.pku.edu.cn/JudgeOnline/problem?id=1038 Bugs Integrated,inc.在刘汝佳的书上有解答,还有著名的“炮兵阵地”一题,及Hamilton路,TSP问题(http://acm.pku.edu.cn/JudgeOnline/problem?id=2288 Islands and Bridges)等。

基本思想就是“状态压缩”,通常是位压缩,涉及位的运算,通常复杂度会比较高(指数级)。

贴一下炮兵阵地的代码:

 

#include  < iostream >
#define  N 100
#define  M 10
#define  MAXSTATE 59049
using   namespace  std;

int  mi[] = { 1 , 3 , 9 , 27 , 81 , 243 , 729 , 2187 , 6561 , 19683 };

int  cannon[N + 1 ][MAXSTATE] = { 0 },maxState,mV = 0 ;    //  canno[i][j]--the i row in state j(old state, i-1 row more accurately) hold that many

char  deploy[N][M] = { 0 };

int  m,n,re =- 1 ;

void  input()
{
    
int  i,j;

    cin
>> n >> m;

    
for  (i = 0 ;i < n;i ++ )
    {
        
for  (j = 0 ;j < m;j ++ )
            cin
>> deploy[i][j];
    }

    maxState
= mi[m - 1 ] * 3 ;

    
}

int  a[M],cannonAdd;  //  to record state in  3.

void  decode( int  s)
{
    
int  i;
    
for  (i = 0 ;i < m; ++ i)
    {
        a[i]
= s % 3 ;
        s
/= 3 ;
    }
}

int  encode()
{
    
int  s = 0 ;
    
for  ( int  i = 0 ;i < m;i ++ )
    {
        s
+= a[i] * mi[i];
    }
    
return  s;
}

void  place ( int  i, int  j, int  org) //  place canno in i row ,from j col, current bit is s
{
    
if  (j == m)
    {
        
int  s = encode();
        
if  (cannon[i][org] + cannonAdd > cannon[i + 1 ][s])
        {
            cannon[i
+ 1 ][s] = cannon[i][org] + cannonAdd;
            
if  (cannon[i + 1 ][s] > mV)
            {
                mV
= cannon[i + 1 ][s];
            }
        }
        
return  ;
    }

    
if  (a[j] > 0 ) //  cannot place 
    {
        
-- a[j];
        place(i,j
+ 1 ,org);
        
++ a[j];
    }
    
else
    {
        place(i,j
+ 1 ,org);
        
if  (deploy[i][j] == ' P ' && a[j - 1 ] != 2 && a[j - 2 ] != 2 )
        {
            a[j]
= 2 ;
            
++ cannonAdd;
            place(i,j
+ 1 ,org);
            a[j]
= 0 ;
            
-- cannonAdd;
        }
    }
}

void  solve()
{
    
int  i,j;

    
for  (i = 0 ;i < n;i ++ )
    {
        
for  (j = 0 ;j < maxState;j ++ )
        {
            
if  (cannon[i][j] + 10 < mV) continue ;
            decode(j);
            cannonAdd
= 0 ;
            place(i,
0 ,j);
        }
    }
}


int  main()
{
    input();

    solve();

    cout
<< mV << endl;

    
return   0 ;
}

 

  相关解决方案