正文

状态压缩dp初探(代码片段)

scl0725  scl0725  2022-12-11  182

关键词：

状态压缩DP 初探

+++

1.蒙德里安的梦想

求把NM的棋盘分割成若干个12的的长方形，有多少种方案。

例如当N=2，M=4时，共有5种方案。当N=2，M=3时，共有3种方案。

如下图所示：

技术图片

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数N和M。

当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

1≤N,M≤111≤N,M≤11

输入样例：

输出样例：

题解：

我们可以分析横着放方块的方案数，即为答案数。

按列分析，如果此列想要放置一个横向方块，那么i - 1列就不可以捅到第i列（即此位置无位于i - 1列和i列的横向方块），我们可以用j & k来判断此情况，其中j是枚举第i列的状态，k是枚举i - 1列的状态。

其次，为了可以让空位置可以让竖向方块刚好填满，那么第i列就不可以有连续奇数个0，用j | k来判断此情况。

最后做一遍dp即可。

状态表示：f[i] [j] 表示第i列状态是j的方案数，j则表示的是i - 1列捅到第i列的状态（一个二进制数）。

状态属性：max，最大方案数

AC代码：

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

using namespace std;

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

long long f[N][M];
int n, m;
bool st[M];

int main()

    while (cin >> n >> m, n || m)
    
        //预处理st数组
        for (int i = 0; i < 1 << n; i ++ )
        
            st[i] = true;
            
            int cnt = 0;
            for (int j = 0; j < n; j ++ )
                if(i >> j & 1)
                
                    if(cnt & 1) st[i] = false;
                    cnt = 0;
                
                else cnt ++ ;
            
            if(cnt & 1) st[i] = false;
        
        
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        
        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ )
                for (int k = 0; k < 1 << n; k ++ )
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        
        cout << f[m][0] << endl;
    
    
    return 0;

算法竞赛专题解析（15）：dp应用--状态压缩dp(代码片段)

...（1）QQ群，567554289；（2）作者QQ，15512356目录1、引子2、状态压缩DP的原理3、poj24114、hdu45395、三进制状态压缩1、引子??提到状态压缩DP时，常常用Hamilton问题作为引子。最短Hamilton路径https:/ 查看详情

poj292301背包+状态压缩/状压dp(代码片段)

题目链接EmmaandEricaremovingtotheirnewhousetheyboughtafterreturningfromtheirhoneymoon.Fortunately,theyhaveafewfriendshelpingthemrelocate.Tomovethefurniture,theyonlyhavetwocompactcars,whichcomplicatesevery 查看详情

cornfields状态压缩dp(代码片段)

题目:FarmerJohnhaspurchasedalushnewrectangularpasturecomposedofMbyN(1≤M≤12;1≤N≤12)squareparcels.Hewantstogrowsomeyummycornforthecowsonanumberofsquares.Regrettably,someofthesquaresareinfertileandcan’tbeplanted.CannyFJknowsthatthecowsdislikeeatingclosetoeachother,sowhenchoosingwhichsquares... 查看详情

15.蒙德里安的梦想状态压缩dp(代码片段)

位运算+二进制表示状态= 状态压缩DP 先把横着的小方块放好，然后剩下位置用竖着的小方块填充然后就转化为求横着摆放小方块的方案数按列来求状态表示： dp[i][j]表示所有摆到了第i列，然后上一列伸出来... 查看详情

poj3071football-状态压缩+期望dp(代码片段)

DescriptionConsiderasingle-eliminationfootballtournamentinvolving2n teams,denoted1,2,…,2n.Ineachroundofthetournament,allteamsstillinthetournamentareplacedinalistinorderofincreasingindex.Th 查看详情

poj3254cornfields(状态压缩dp入门)(代码片段)

DescriptionFarmerJohnhaspurchasedalushnewrectangularpasturecomposedof M by N (1≤ M ≤12;1≤ N ≤12)squareparcels.Hewantstogrowsomeyummycornforthe 查看详情

1349.maximumstudentstakingexam（dp，状态压缩）(代码片段)

题目MaximumStudentsTakingExamAddtoListShareGivenam*nmatrixseatsthatrepresentseatsdistributionsinaclassroom.Ifaseatisbroken,itisdenotedby‘#‘characterotherwiseitisdenotedbya‘.‘character.Studentscanseetheanswersofthosesittingnexttotheleft,right,upperleftandupperright,buthecannotseetheanswerso... 查看详情

codeforces580dkefaanddishes(状态压缩dp)(代码片段)

...大，请求出满意度。解题思路：状压DP，设dp[i][j]表示在状态i并且最后一道菜放在位置j时的最大满意度。注意要处理好一道菜时的情况，以及注意二进制查看详情

动态规划_计数类dp_数位统计dp_状态压缩dp_树形dp_记忆化搜索(代码片段)

...计DP题目链接：题目大意：思路：代码：状态压缩DP蒙德里安的梦想题目大意：思路：代码最短Hamilton路径题目大意思路代码树形dp原题链接:题目大意思路代码记忆化搜索原题链接：题目大意：思路&#... 查看详情

状压dp(代码片段)

目录状态压缩DP1.状态压缩的定义2.位运算3.入门例题状态压缩DP1.状态压缩的定义状态压缩的定义：我们知道任何一个二进制都可以对应唯一的十进制数，反过来也成立。所以我们可以用一个数来代替一组数从而降低维数。这种解... 查看详情

dp状态压缩之棋盘问题(代码片段)

写在前面状态压缩的思想是将难以用机器语言表达具象的现实实物进行抽象.常常用二进制数来表达一种状态比方说有A、B、C，三个方案，2=010表示不选A，选B，不选C的方案，于是要枚举所有方案只需要枚举0... 查看详情

0x56.动态规划-状态压缩dp（习题详解×7）(代码片段)

目录ProblemA.最短Hamilton路径ProblemB.蒙德里安的梦想ProblemC.CornFieldsProblemD.小国王ProblemE.炮兵阵地ProblemF.宝藏ProblemG.JoggingTrails（中国邮递员问题，欧拉回路）本系列博客是《算法竞赛进阶指南》的学习笔记，包含书中... 查看详情

a-mondriaan'sdream（状态压缩dp）(代码片段)

SquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthedrawingsinhis‘toiletseries‘(wherehehadtousehistoiletpapertodrawon,forallofhispaperwasfilledwithsquaresandrectangles),hedreamtoffillingalargerectanglewithsmallrectanglesofwidth2andheight1invaryingways.Exper... 查看详情

poj1185炮兵阵地（状态压缩dp)(代码片段)

POJ飞翔.数据弱ZQOJ飞翔数据强Description司令部的将军们打算在N×M的网格地图上部署他们的炮兵部队。一个N×M的地图由N行M列组成，地图的每一格可能是山地（用"H"表示），也可能是平原（用"P"表示），如下图。在每一格平原... 查看详情

luogup2051[ahoi2009]中国象棋dp状态压缩+容斥(代码片段)

参考：https://www.luogu.com.cn/blog/RPdreamer/p2051#include<map>#include<queue>#include<time.h>#include<limits.h>#include<cmath>#include<ostream>#include<iterator&g 查看详情

[状态压缩dp]leetcode5.02双周赛每个人戴不同帽子的方案数(代码片段)

...时参加周赛的时候没做出来，后来通过看题解，学习到了状态压缩dp,对于这一题是理解了，但是状态压缩dp运用的还不是特别好。记录一下解题过程。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/number-of-ways-to-wear-different... 查看详情

poj2441状态压缩dp基础(代码片段)

...仓只能有一头牛问可行的安排方式dp[i][j]表示前i头牛组成状态j的方案数，状态0表示无牛，1表示有牛使用滚动数组即可枚举到第i头牛时，状态j必须有i-1头牛，然后由这个状态推导出第i头牛的状态，再清0*/#include<iostream>#inclu... 查看详情

acwing291.蒙德里安的梦想（状态压缩dp）(代码片段)

题目链接https://www.acwing.com/problem/content/293/思路我们用一个n位二进制表示一列的情况，那么一列的情况有2n2^n2n种，我们枚举塞1×21\\times21×2的方块数量，那么最后塞入2×12\\times12×1的方块的数量也是固定了的，我们... 查看详情