地图网站抓取,网站三大标签修改注意事项,网站推广seo设置,怎么推广店铺蒙德里安的梦想 核心思想#xff1a; 状态压缩dp 总方案 横放的方案 剩下的地方竖着放是固定的了 状态压缩 #xff1a; 将每一列的图(横终点 横起点 竖) 用一个二进制数存下 向后凸的为1 反之为0 状态计算#xff1a; 所有 i – 1 列 不冲突的 都加和 f[i , j] f[i - 1…蒙德里安的梦想 核心思想 状态压缩dp 总方案 横放的方案 剩下的地方竖着放是固定的了 状态压缩 将每一列的图(横终点 横起点 竖) 用一个二进制数存下 向后凸的为1 反之为0 状态计算 所有 i – 1 列 不冲突的 都加和 f[i , j] f[i - 1 , k] …. … **不合法状态**前两种合法 后两种不合法 单个格子不能竖放 不冲突状态 ①j k 0 没重叠部分 ②j | k 必须是合法的
朴素版 #includeiostream#includecstring#includealgorithmusing 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(cinnm , n || m) //有输入 且均不为0{for(int i0;i 1 n ; i) //i2的n次方//一共n行 每个位置两种选择 共2的n次方{int cnt 0; //记录一张图连续的0有多少个st[i] true; //初始i图为true合法的for(int j0;jn;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列 不放方块 方案 1for(int i1;im;i) //遍历每一列for(int j0;j 1 n; j) //每列2的n次方张图for(int k0;k 1 n;k) //前一列也是2的n次方张图if((j k) 0 st[j | k]) //不冲突的条件f[i][j] f[i-1][k]; //计算coutf[m][0]endl; //输出前m-1列排好序 没有凸出来的方案数}}优化版 #includeiostream#includecstring#includealgorithm#includevectorusing namespace std;const int N 12 , M 1 N ;int n,m;long long f[N][M];bool st[M];vectorvectorint state(M); //用二维数组将与 j 不冲突的k存下 不用去再遍历了int main(){while(cinnm , n || m){for(int i0;i 1 n ; i){int cnt 0;st[i] true;for(int j0;jn;j){if(i j 1){if(cnt 1){st[i] false;break;}cnt 0 ;}else cnt;}if(cnt 1) st[i] false;}for(int j0;j 1n;j){state[j].clear(); //清空之前的for(int k0;k 1n;k){if((j k) 0 st[j | k])state[j].push_back(k); //不冲突放里头}}memset(f,0,sizeof f);f[0][0] 1;for(int i1;im;i)for(int j0;j 1 n; j)for(auto k : state[j]) //不冲突的已经存起来了 取出f[i][j] f[i-1][k];coutf[m][0]endl;}}
