题目链接：?id=2411题目大意：用1*2的小矩形拼成h*w的大矩形有多少种方法题目分析：首先如果大矩形面积为奇数肯定不能拼成，否则因为h和w都不是很大，我们采用状态压缩的思想，用1表示竖着的状态，0表示横着的状态，比如说上图中的第一第二行状态为：0 0 1 0 0 0 0 1 1 0 01 1 1 1 0 0 1 1 1 0 0，dp[i][j]表示第1行状态为j时的方法数，显然对于竖着的状态，竖着的上部分所在的行对下部分是有影响的，而横着的状态只对当前行有影响，我们先考虑横着的，因为小矩形面积为2，所以在两个相邻的竖着状态的格子间横着状态占的格子数必然为偶数个例如1 0 0 0 1，这样0的格子显然不能组成完整的横着的状态，而1 0 0 1就可以，下面考虑竖着的状态，我们从第一行开始，如果是竖着的，则对下一行有影响，及上一行为1则当前行对应的列必为1，这样我们就可以把当前行为1的地方置为0（因为其状态已经由上一行的1唯一确定）这样改是为了使上一行&当前行的值为0，以此当作竖着条件下的合法状态，因为如果上一行为0则当前行可以为0或者1，上一行为1当前行必为0，与的结果都是0，也就是说我们把1 0 0 1 1 0 0 11 0 0 0，当作竖着的非法状态, 0 0 0 0，，当竖着的合法状态，横着的合法状态上面已经说了，我们可以用一个函数来判断。初始化dp[0][0]为1，从第一行一直推到第h行，答案即为dp[h][0]，意思是第h行状态为0的方法数，这里状态为0相当于不给它状态，因为最后一行的状态已经由其上一行唯一确定，换句话说，最后一行没有一个格子的状态是不确定的，要么作为竖着的下半部分要么是横着的合法状态#include <cstdio>#include <cstring>#define ll long longll dp[12][(1 << 12)];int h, w;bool ok(int t){int cnt = 0;for(int i = 0; i < w; i++){if(t & 1){if(cnt & 1) //判断相邻两个1之间0的个数return false;}elsecnt++;t >>= 1;}if(cnt & 1) //判断最后一个1左边0的个数return false;return true;}int main(){while(scanf("%d %d", &h, &w) != EOF && (w + h)){if((h * w) & 1) //面积为奇数不可能拼成，因为一个单位面积就为偶数了{printf("0\n");continue;}memset(dp, 0, sizeof(dp));dp[0][0] = 1;for(int i = 1; i <= h; i++)for(int j = 0; j < (1 << w); j++)for(int k = 0; k < (1 << w); k++)if(((k & j) == 0) && ok(k ^ j))dp[i][j] += dp[i – 1][k];printf("%lld\n", dp[h][0]);}}
在繁华中体会热闹;若是厌倦了喧嚣，寻一处宁静的幽谷，
