pku 1632 Vase Collection_综合

这道题用了状态压缩。

状态压缩常常用在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 ;
}