算法基础之蒙德里安的梦想

2023-12-29 21:40:25

蒙德里安的梦想

  • 核心思想: 状态压缩dp

    • 总方案 = 横放的方案 剩下的地方竖着放是固定的了

    • 状态压缩 : 将每一列的图(横终点 横起点 竖) 用一个二进制数存下

      • 向后凸的为1 反之为0
      • 在这里插入图片描述
    • 状态计算: 所有 i – 1 列 不冲突的 都加和

      • f[i , j] = f[i - 1 , k] + …. + …
      • 在这里插入图片描述
    • **不合法状态:**前两种合法 后两种不合法 单个格子不能竖放

      • 在这里插入图片描述
    • 不冲突状态:j & k ==0 没重叠部分j | k 必须是合法的

      • 在这里插入图片描述

朴素版

  •   #include<iostream>
      #include<cstring>
      #include<algorithm>
      
      using namespace std;
      const int N = 12 , M = 1 << N ;  //M为图的最大数 2的N次方
      
      int n,m;
      long long f[N][M];  //开long long的f存
      bool st[M];  //标记该图是否合法
      
      int main()
      {
          while(cin>>n>>m , n || m)  //有输入 且均不为0
          {
              for(int i=0;i< 1 << n ; i++)  //i<2的n次方
                  //一共n行 每个位置两种选择 共2的n次方
              {
                  int cnt = 0;  //记录一张图连续的0有多少个
                  st[i] = true;  //初始i图为true合法的
                  for(int j=0;j<n;j++)  //遍历图中每位数
                  {
                      if(i >> j & 1)  //取i图中第j个数 判断是否为1
                      {  //若为1 则判cnt是奇数偶数
                          if(cnt & 1)  //奇数则说明 图不合法
                          {
                              st[i] = false; //有奇数0 直接false 退出循环
                              break;
                          }
                          cnt = 0 ;  //清空cnt 重新开始
                      }
                      else cnt++;  //若为0 cnt++
                  }
                  if(cnt & 1) st[i] = false;  //判断后段0的个数 没有1 进不去上面的判断 
              }
              
              memset(f,0,sizeof f);  //初始化
              f[0][0] = 1;  //0列 不放方块 方案 = 1
              for(int i=1;i<=m;i++)  //遍历每一列
                  for(int j=0;j< 1 << n; j++)  //每列2的n次方张图
                      for(int k=0;k< 1 << n;k++)  //前一列也是2的n次方张图
                          if((j & k) == 0 && st[j | k])  //不冲突的条件
                              f[i][j] += f[i-1][k];  //计算
              cout<<f[m][0]<<endl;  //输出前m-1列排好序 没有凸出来的方案数
          }
      }
    

优化版

  •   #include<iostream>
      #include<cstring>
      #include<algorithm>
      #include<vector>
      
      using namespace std;
      const int N = 12 , M = 1 << N ;
      
      int n,m;
      long long f[N][M];
      bool st[M];
      vector<vector<int>> state(M);  //用二维数组将与 j 不冲突的k存下 不用去再遍历了
      
      int main()
      {
          while(cin>>n>>m , n || m)
          {
              for(int i=0;i< 1 << n ; i++)
              {
                  int cnt = 0;
                  st[i] = true;
                  for(int j=0;j<n;j++)
                  {
                      if(i >> j & 1)
                      {
                          if(cnt & 1)
                          {
                              st[i] = false;
                              break;
                          }
                          cnt = 0 ;
                      }
                      else cnt++;
                  }
                  if(cnt & 1) st[i] = false;
              }
              
              for(int j=0;j< 1<<n;j++)
              {
                  state[j].clear();  //清空之前的
                  for(int k=0;k< 1<<n;k++)
                  {
                      if((j & k) == 0 && st[j | k])
                          state[j].push_back(k);  //不冲突放里头
                  }
              }
              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(auto k : state[j])  //不冲突的已经存起来了 取出
                          f[i][j] += f[i-1][k];
              cout<<f[m][0]<<endl;
          }
      }
    

文章来源:https://blog.csdn.net/Pisasama/article/details/135297936
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。