Acwing 状态压缩 DP

Acwing 291.蒙德里安的梦想

输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
0
1
2
3
5
144
51205

实现思路：先放横着的，再放竖着的。
总方案数，等于只放横着的小方块的合法方案数。（放完横着的方块之后，竖着的只能被动填充进去，不需要进行额外进行竖着的情况）

• 方案合法的条件是：当横着的方块放完后，竖着的小方块恰好能把剩余的地方全部填满
  • 那如何判断方案是否合法呢？即怎么看竖着的小方块是否能把剩余部分填满呢？
  • 因为是竖着放的，所以可以按列来看，每一列的内部，只要所有连续的空余小方块的个数为偶数即可。
• 状态表示：f[i][j]表示前i-1列已经摆好，且从第i-1列是否有伸出一格到第i列的情况（这个情况用j`表示）的所有方案数。
  • 对于j：j是一个二进制数，位数与棋盘的行数相等，比如N=5，M=5的棋盘，j为5位的二进制数(XXXXX)_2，但在程序中还是用十进制数表示。（所以要用位运算来判断某一位是1或0）
  • 什么叫j表示从第i-1列伸出一格到第i列的情况？如下图，第i列的第1，2，5个格子，是从i-1列伸过来的。此时的状态j为 (11001)_2，即对于第i列的所有格子，第1，2，5个格子被伸出来占据了（j是个二进制数，若该列的某一行，有被前面的列伸出来一格，则用1表示，否则用0表示），那么这些个位置被侵占了，就不能再横放了。
  • 这样对f[i][j]更通俗的理解就是第i列的横放情况，由j的二进制表示出第i列哪些行可以横放
• 状态转移：既然第i列固定了，我们需要看 第i-2 列是怎么转移到到第 i-1列的（看最后转移过来的状态）。假设此时对应的状态是k（第i-2列到第i-1列伸出来的二进制数，比如00100），k也是一个二进制数，1表示哪几行小方块是横着伸出来的，0表示哪几行不是横着伸出来的。它对应的方案数是 f[i−1,k]，即前i-2列都已摆完，且从第i-2列伸到第i-1列的状态为 k 的所有方案数。
• 那k需要满足什么条件，才能够从f[i - 1][k]转移到f[i][j]呢？
  • ①k和j不能冲突，也就是第i-1列和第i列的不能有重叠的1，即两列的相同行不能同时为1（不能同时有前一列伸过来的）。如下图，在第一行k的二进制位为1，j的二进制位也为1，那么第i列就不能再横放东西了。转化为代码判断就是** (k & j ) ==0** ，表示两个数相与，如果两有对应位同时为1，则相与结果为1，否则为0即没有冲突。
    
  • ②既然从第i-1列到第i列横着摆的，和第i-2列到第i-1列横着摆的都确定了，那么第i-1列 空着的格子就确定了，这些空着的格子将来用作竖着放。如果 某一列有这些空着的位置，那么该列所有连续的空着的位置长度必须是偶数（即不能有奇数个0）。设置一个st[]数组表示的是这一列连续0的个数的情况，若为true表示连续偶数个0（合法状态），否则为false。体现到代码判断第i-1列满足竖放的合法状态：st[k|j]=true，
    • 解释：第i-1列中1的总个数，就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的
      • st[k]表明第i-2列插入到i-1列的1的个数，i-1列被动生成的1
      • st[j]表明第i-1列插入到i列的1的个数，也就是i-1列自己生成的1
• 最后结果输出f[m][0]
  • 对于f[0][0]=1和最后输出f[m][0]理解：数组下标从0开始表示实际棋盘的第一列，放f[][]表示当前列的横放情况,f[0][0]表示当前一列没有伸过来的（因为前面根本没有列），所以也就没有横放的情况，只有竖放的情况，即f[0][0]=1。所以输出f[m][0]表示第m列不横放，这也是合理的，如果第m列横放了，那就超出m列的范围了。

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 12,M = 1 << N;

long long f[N][M];
bool st[M];//记录当前连续0的个数是否为偶数 ，即合法状态为true
int n,m;

int main(){
    while(cin >> n >> m, n || m){
        memset(f,0,sizeof f);
        
        //先预处理得到每一列连续0的个数 是偶数还是奇数
        for(int i = 0 ; i < 1 << n ; i ++){
            st[i] = true;
            int cnt = 0;//记录0的个数
            
            for(int j = 0; j < n ; j ++){//遍历当前列的每一行
                if(i >> j & 1){//取得当前列的一位 若为1
                    //判断之前记录的0的个数 是否为奇数
                    if(cnt & 1) st[i] = false;//若为奇数 标记为不合法
                }
                else cnt ++;//取得当前行的一位 为0
            }
            //得到该列0个数的最终结果 判断是否合法
            if(cnt & 1) st[i] = false;
        }
        f[0][0] = 1;
        
        //开始DP
        for(int i = 1 ; i <= m ; i ++){//从列开始
            for(int j = 0 ;j < 1 << n ; j ++){//第i列情况
                for(int  k = 0 ; k < 1 << n ; k ++){//第i-1列情况
                    if((j & k) == 0 && st[j | k])//若没有冲突 且连续0的个数为偶数 | 按位或
                       f[i][j] += f[i - 1][k];//合法
                }
            }
        }
        cout << f[m][0] << endl;
    }
    return 0;
}

Acwing 91.最短Hamilton路径

实现思路：

• f(i,j)表示从0号点到j号点，且中间经过点的状态是i（和上题类似，用二进制表示，位为1就表示某点经过，同样要进行位运算来获得每一位。如 1 1 1 0 1 表示第0，1，2，4被走过）的最短路径长度。
• 集合划分：最后一个点是j，按倒数第二个点划分，若倒数第二个点是k，即从0号点经过一系列不重复的点到达点k，再经过点k到达终点j。同时在这个状态i中就不能再包括点j了（因为路径要不重不漏），要再状态i中除去j。
• 最终状态转移方程为：f[i][j]=min(f[i][j],f[i-1<<j][k]+a[k][j])；因为i是二进制数，除去j点就表示使j位置上的二进制位由0后改为1，即相减。

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 21,M = 1 << N;

int n;
int f[M][N],a[N][N];

int main(){
    cin >> n;
    for(int i = 0 ; i < n; i ++){
        for(int j = 0 ; j < n ; j ++){
            cin >> a[i][j];
        }
    }
    
    memset(f,0x3f,sizeof f);//初始化图上距离为无穷大
    f[1][0] = 0;//从0开始到0本身的距离为0
    
    for(int i = 1 ; i < 1 << n ; i ++){
        for(int j = 0 ; j < n ; j++){//枚举0到n号点
            if(i >> j & 1){//为1要到达点j
                for(int k = 0 ; k < n ; k ++){//枚举倒数第二个点k
                    if((i - (1 << j)) >> k & 1)//如果k在路径中
                       f[i][j] = min(f[i][j],f[i - (1 << j)][k] + a[k][j]);
                }
            }
        }
    }
    //从0经过所有点 到达n - 1号点
    cout << f[(1 << n) - 1][n - 1];
    
    return 0;
}

这两道题目是竞赛题，难度有点大。就在此记录一下把~