算法基础之蒙德里安的梦想
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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!