状态压缩

如果有一个状态,是由很多(<20)个状态组合起来的,就可以用状态压缩减少空间复杂度。
我们把每一个子状态作为二进制的一位,可以表示其是和否。

例题

传送门

解题思路

我们把每一种组合作为一种状态,例如:
第一行是

12345
10011

选择只第一个1

dp[1][2^0]

如果全部把所有的1都选择,就把状态压缩为

dp[1][2^0+2^1+2^4]//(从右到左)

即为

dp[1][19]

状态转移方程比较复杂,看下面代码吧。

//n * m的01矩阵(1 <= n,m <= 12)
//不考虑选择的块数,问多少种选择方案
//不选择两块相邻的矩阵
//0表示不可选择
#include <iostream>
#include <cmath>
using namespace std;
const int mod = 1e8;
/*
dp[i][j]  //第i行 在j状态下有几种方案
*/
int dp[12][1<<12],cur[12];//cur[i]代表第i行的选择情况 
bool vis[1 << 12];//标记状态是否合法

int main(){
    int m,n;
    cin>>m>>n;
    int matrix[20][20];
    for(int i=0;i<m;i++){
        cur[i] = 0;
        for(int j=0;j<n;j++){
            cin>>matrix[i][j];
            if(matrix[i][j] == 0) cur[i] += (1 << j);//对每一行的状态初始化
        }
    }
    int bit = (1 << n) - 1,x;
    for(int i = 0;i <= bit;i++){
        for(int j = 0;j < m;j++) dp[j][i] = 0;
    }
    for(int i = 0;i <= bit;i++){
        vis[i] = true;
        x = i;
        while(x){
            if((x & 1) != 0 && (x & 2) != 0){
                vis[i] = false;
                break;
            }
            x >>= 1;
        }
                if(vis[i] && (cur[0] & i) == 0) dp[0][i] = 1;
                else dp[0][i]=0;
    }
    for(int i = 1;i < m;i++){//递推每一行
        for(int j = 0;j <= bit;j++){//枚举当前行状态
            if((cur[i] & j) != 0) continue;//当前行和目标矩阵是否合法
            if(!vis[j]) continue;//看状态是否合法
            for(int k = 0;k <= bit;k++){//从上一行的k状态转移过来
                if((k & j) != 0) continue;//上一行和这一行的状态能否转移
                if(!vis[k]) continue;//看状态是否合法
                dp[i][j] = (dp[i][j] +  dp[i - 1][k]) % mod;
            }
        }
    }
    int ans = 0;
    for(int i = 0;i <= bit;i++) ans = (ans + dp[m - 1][i]) % mod;
    cout << ans << endl;
    return 0;
}

本文链接:https://kaispace.com.cn/index.php/archives/338/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者