[动态规划](6)状压DP

蒙德里安的梦想

image-20210707172304222

引言:

所谓的状态压缩DP,就是用二进制数保存状态,为什么不直接用数组记录呢?因为用一个二进制数记录方便作位运算。

核心思路:

  • 先放横着的小方块,再放竖着的
  • 总方案数,等于只放横着小方块的合法方案数
  • 当前方案合法条件

    • 所有的剩余位置,能否填充满竖着的小方块
    • 可以按列来看,每一列内部,只要所有连续的空着的小方块需要偶数

      • 如果是奇数,必然会有一个小方块放不了

这题配合视频加代码看最好,导图不起作用 AcWing 291. 蒙德里安的梦想(《算法竞赛进阶指南》打卡活动) - AcWing

代码:

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N = 12, M = 1 << N;//最后状态需要取到f[最后一行+1][0]
long long f[N][M];//第一维表示列,第二维表示所有可能的状态
bool st[M];//存储每种状态是否又奇数个连续的0,如果奇数个0是无效状态,如果是偶数个零则置为true
vector<int> state[M];//动态数组,自动增加一个为M列的一维数组的容器
int m, n;
int main() {
    while (cin >> n >> m, n || m) {//读入n和m,并且不是两个0既合法输入就继续读入
        //第一部分:预处理1
        //对于每种状态,先预处理每列不能又奇数个连续的0
        for (int i = 0; i < 1 << n; i++) {//枚举每种状态
            int cnt = 0;//记录连续的0的个数
            bool isValid = true;//某种状态没有奇数个连续的0则标记为true

            for (int j = 0; j < n; j++) {//遍历这一列,从上到下
                if (i >> j & 1) {//i>>j位运算,表示i(i在此处是一种状态)的二进制的第j位是1的话
                    if (cnt & 1) {//看前面连续的0的个数,如果是奇数(cnt&1为真),则该状态不合法
                        isValid = false;
                        break;
                    }
                    cnt = 0;//既然该位是1,并且前面不是奇数个0(经过上面if的判断),计数器清零
                }
                else cnt++;//否则的话该位还是0,则统计连续0的计数器++
            }
            if (cnt & 1) isValid = false;
            st[i] = isValid;
        }


        //第二部分:预处理2
        //经过上面每种状态,连续0的判断,已经筛掉一些状态
        //下面来看进一步的判断:看第i-2列伸出来的和第i-1列伸出去的是否冲突

        for (int j = 0; j < 1 << n; j++) {//对于第i列的所有状态
            state[j].clear();//清空上次操作遗留的状态,防止影响本次状态
            for (int k = 0; k < 1 << n; k++) {//对于i-1列所有状态
                if ((j & k) == 0 && st[j | k])//第i-2列伸出来的和第i-1列伸出来的不冲突(不在同一行)
                    //这里st[j|k]的含义:
                    //1.我们已经知道st[]数组表示的是这一列没有连续奇数个0的情况
                    //2.我们要考虑的是第i-1列(第i-1列是这里的主体)中从i-2列横插过来的,还要考虑自己这一列(i-1)列横插到第i列的
                    //3.比如 第i-2列横插过来的是k=10101,第i-1列插出去到第i列的是 j = 01000
                    //4.那么合在第i-1列,到底又多少个1呢?自然想到的就是这两个操作的共同结果:两个状态或, j|k = 01000 | 10101 = 11101
                    //5.这个 j|k就是当前第i-1列到底有几个1,既哪几行是横着放格子的
                    //----例如上列11101既不合法----

                    state[j].push_back(k);//二维数组state[j]表示第j行
                    //j表示 第i列"真正"可行的状态.如果第i-1列的状态k和j不冲突则压入state数组中的第j行
                    //"真正"可行是指:既没有前后两列伸进伸出的冲突;又没有连续奇数个0
            }
        }
        //第三部分:dp开始
        memset(f, 0, sizeof f);//全部初始化位0,因为是连续读入,这里是一个清空操作,类似上面的state[j].clear()
        f[0][0] = 1;//这里需要回忆状态表示的定义,按定义这里是:前第-1列第都摆好.且从-1列到第0列伸出来的状态为0的方案数
        //首先,这里没有-1列,最少也是0列,其次,没有伸出来,既没有横着摆的,既这里第0列只有竖着摆这一种状态

        for (int i = 1; i <= m; i++) {//遍历每一列:第i列合法范围是(0到m-1列)
            for (int j = 0; j < 1 << n; j++) {//遍历当前列(第i列的所有状态j)
                for (auto k : state[j])//遍历第i-1列的状态k,如果"真正"可行,就转移
                    f[i][j] += f[i - 1][k];//当前列的方案数就等于之前第i-1列所有状态k的累加
            }
        }
        //最后答案是什么呢?
        //f[m][0]表示前m-1列都处理完,并且m-1列没有伸出来的所有方案数
        //既整个棋盘都处理完的方案数
        cout << f[m][0] << endl;

    }
    return 0;
}

最短Hamilton路径

image-20210707174212674

核心思路:

  • 如何表示哪些点已经被经过,哪些点没有被经过?可以使用一个 n 位的二进制数 ,若其第 i 位(0<=i<n) 为 1 ,则表示第 i 个点已经被经过,反之未被经过
  • 在任意时刻还需要只要当前所处的位置,因此我们可以使用 fi ( 0 <= i <= 2^n,0<=j<n),表示"点被经过的状态" 对应的二进制数为i ,且目前处于点 j 时的最短路径。
  • 在起点时,有 f1=0,即只经过了点0(i只有第0位为1) ,目前处于起点0,最短路径长度为0,方便起见,我们将f数组其他的值设为无穷大,最终目标是 f(1<<n)-1,即经过所有点(i的所有位都为1),处于终点 n - 1 的最短路

这题也直接配合视频看代码比较好,AcWing 91. 最短Hamilton路径 - AcWing

代码:

#include<iostream>
#include<cstring>
using namespace std;
int n,f[1<<20][21];
int weight[21][21];
int main(){
    ios::sync_with_stdio(false);//加快cin的读入速度,但同样禁止了scanf
    cin>>n;
    memset(f,0x3f,sizeof f);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>weight[i][j];//读入权值

    f[1][0]=0;//第一个点是不需要任何费用的

    for(int i=1;i<1<<n;i++)//i表示着是一个方案集合,其中每一个位置1和0,代表着这个点经过还是没有经过
        for(int j=0;j<n;j++)//枚举当前到了哪个点
            if(i>>j&1)//如何当前方案中到达了j这个点
                for(int k=0;k<n;k++)//枚举到达j的每个点k
                //枚举到达j点的所有上一个状态
                    if((i^1<<j)>>k&1)//i^1<<j的作用是将第j位清0,然后右移到k看当前路径是否能从k到j
                    f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]); //与当前取最小值


    cout<<f[(1<<n)-1][n-1]<<endl;//输出最后最优值
    return 0;
}

本文链接:

https://nullcode.fun/155.html
1 + 3 =
快来做第一个评论的人吧~