安徽省同济建设集团网站,四川seo推广公司,深圳服务平台网站,自动友链网题目描述 题目分析
显而易见的重要事实
首先#xff0c;需要明白一个很重要的事实#xff1a;
所有的摆放方案数所有横着摆放且合理的方案数
这是因为#xff0c;横着的确定之后#xff0c;竖着的一定会被唯一确定#xff0c;举一个例子#xff1a;
------唯一确定-…题目描述 题目分析
显而易见的重要事实
首先需要明白一个很重要的事实
所有的摆放方案数所有横着摆放且合理的方案数
这是因为横着的确定之后竖着的一定会被唯一确定举一个例子
------唯一确定-----
所以使用动态规划进行状态表示的时候仅仅需要考虑横着的长方形即可
状态表示
随后我们来看状态表示
f[i,j]表示前i-1列已经摆好且从第i-1列伸出到第i列的状态为j的所有方案数
注意列数的下标是0~m-1
举一个例子 如上图假设一个6*6棋盘前两列已经以如图方式摆好此时对于第三列的第一、四行有被第二列伸过来的部分所以此时第二列的状态就是100100将这个字符串看成二进制数转为十进制为36所以这就是f[2,36]所指的“所有方案数”的其中一个。
状态计算
对于同一列i即使j值状态数相同也会因为前i-1列的摆放方案不同而导致整体的摆放方案不同也就是说在前i-1列已经确定的情况之下第i-1列的每一个状态的每一个方案都能够组合一个第i列的确定的状态j得到一个新的摆放方案 比如上述这个图列3的状态为101010由于列2可能存在不同的状态0x0y0z导致整体的摆放方案不同同理列2的某一种状态的方案数也因为列1可能存在不同的状态导致此方案数有可能大于1所以呈现一个递归的现象由此可得状态计算 其中k为第i-1列的状态值可以取不同的值
何时合理
显然对于上述状态计算式子如果不限制k值和j的关系而一味地让k和j取遍整个0~2^n-1就会发生一些不合理的现象比如 假设现在已经处理到i3的情况并且假设i0~i2的所有长方形已经摆好就会发现两个不合理的现象
1.在第一行的列2和列3地方发生了交叉
2.第二行的列2位置有一个不合理空缺这个位置无法再填补任何的长方形因为现在已经假定0~2列是摆好的不会再去这个位置填补空缺的横着放的长方形同时这个地方也根本不可能去放置竖长方形。
为什么产生了这个现象
因为没有约束k和j的关系
我们先来看第一个不合理之处产生的原因(kj)!0
顺便注意一下这里kj一定要加括号因为!的优先级大于
因为如果kj!0那么至少存在一行使得i和i-1列中同时有从i-1和i-2列伸过来的长方形从而导致长方形的重叠
第二个不合理之处的产生原因i-1列中的连续的空缺位置中存在空缺大小为奇数的情况
如何避免这个不合理之处呢
保证st[j|k]true,其中st[x]为true的条件是x的二进制表示中没有奇数个连续的0
边界问题
开头已经说过了此题列的表示下标从0开始所以初始化为f[0][0]1意思是“没有从左边的棋盘边界的外边伸向第一列的长方形的方案数为1”其它f全部初始化为0。
如果列数为m列号从0开始在遍历i的时候最后遍历到的下标是m而不是m-1因为当遍历到第i列的时候实际上保证的是第i-1列的合法性比如刚才那个例子 当遍历到i3的时候发现的两个不合理之处全在i2列。
最后的答案为f[m][0],意思是“在0~m-1列全部摆好的情况之下棋盘右边界的右边一列没有第m列伸过来的长方形的总方案数”
朴素代码以及短路现象
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 12, M 1 N;int n, m;
long long f[N][M];
bool st[M];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;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;
}
在上y总的课时y总说这个代码有一个神奇的现象就是把(j k) 0 st[j | k]中前后的部分进行交换之后时间会变长许多此代码从892ms变为1442ms很显然这与的短路性有关当
(j k) 0不满足时就会跳过st[j | k]的判断因为(j k) 0的“成功率”小于“st[j | k]”的成功率所以会出现上述现象。
优化之后的代码
此代码已经经过优化预处理去除无效状态
#includeiostream
#includecstring
#includevector
using namespace std;
const int N12,M1N;
typedef long long LL;
LL f[N][M];
bool st[M];
vectorintstate[M];//存放j和k的合法映射的集合
int n,m;
int main()
{while(scanf(%d%d,n,m)2(n||m)){for(int i0;i1n;i)//st数组的预处理{int cnt0;st[i]true;for(int j0;jn;j){if(ij1){if(cnt1){st[i]false;break;}cnt0;}else cnt;}if(cnt1)st[i]false;}for(int j0;j1n;j){state[j].clear();//为什么要清空因为是多样例输入for(int k0;k1n;k)if((kj)0st[k|j])state[j].push_back(k);//满足推出f[i][j]的第i-1行的其中一个状态数k}memset(f,0,sizeof f);//因为是多样例输入f[0][0]1;for(int i1;im;i){for(int j0;j1n;j)for(auto k:state[j])//代码优化的体现大大减少了冗余f[i][j]f[i-1][k];}coutf[m][0]endl;}return 0;
}
