最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

【状压DP】蒙德里安的梦想

来源：博客园


(相关资料图)

导读 ^ _ ^

何为状态压缩？

状态压缩的核心是对二进制的理解我们把一个状态表示成二进制从而用一个整数表示出各种状态在dp操作做，我们用位运算的角度去判断并且执行相应的操作

蒙德里安的梦想

思路

如果横着放确定，那么剩下的就是只能竖着放如何表示每行状态，我们将其用二进制去思考，即每个数都是二进制。分类讨论：位运算的补充说明：所以要提取处理一下st布尔数组为什么后面还要对cnt进行判断？因为每次都是从1开始判断，需要处理一下最后的一段

代码实现

#include#include#includeusing namespace std;const int N = 12, M = 1 << 12;long long f[N][M];bool st[M];int n,m;int main( ) {    while(cin >> n >> m, n || m) {        memset(f, 0, sizeof(f));        //预处理st数组，对某种状态不能竖着放的排除        for (int i = 0; i < 1<> j & 1) {                    if(cnt & 1) st[i] = false;                    cnt = 0;                 }                else cnt++;            }            if(cnt & 1) st[i] = false;        }               f[0][0] = 1;//棋盘是从第0列开始，没有-1列，所以第0列第0行，不会有延伸出来的小方块，即1        for (int i = 1; i <= m; i++)            for (int j = 0; j < 1 <

#谢谢你的观看！

^ _ ^

关键词：