泉州有那些网站建设公司,国内建网站软件,建筑培训网安全员,苏州推荐网络公司建网站状态压缩DP 经典覆盖问题#xff0c;输入n和m表示一个n*m的矩形#xff0c;用1*2的方块进行覆盖#xff0c;不能重叠#xff0c;不能越出矩形边界#xff0c;问完全覆盖完整个矩形有多少种不同的方案 其中n和m均为奇数的话#xff0c;矩形面积就是奇数#xff0c;可知是…状态压缩DP 经典覆盖问题输入n和m表示一个n*m的矩形用1*2的方块进行覆盖不能重叠不能越出矩形边界问完全覆盖完整个矩形有多少种不同的方案 其中n和m均为奇数的话矩形面积就是奇数可知是不可能完全覆盖的。接着我们来看n*m为偶数的情况 DP前先处理一下交换n和m使n较大m较小这样能减少状态数 另外数据中是有重复的所以开辟一个ans数组来记录每组数据的结果如果遇到相同的数据则不要计算直接输出答案 不用这个ans数组的话也不会超时这个代码是跑出了950ms加了这个记录答案的数组时间变为600ms 接着就看注释部分的讲解即可 /*
最上面的为第1行最下面为第n行
从上到下按行DP
其中一行的状态我们用一个二进制表示0表示没有被覆盖1表示被覆盖了
最后得到一个01串这个串变回十进制就是一个状态
定义状态dp[i][s]表示前i-1行已经放满第i行的状态为s的方案数
状态转移方程为 dp[i][s]sum{ dp[i-1][ss] } 其中状态s与状态ss兼容
这个状态转移方程的内涵在于理解s和ss何为兼容
首先我们约定一个放置方法就是竖着放的时候我们暂且将其称为“上凸型摆放”
因为竖放必然占据第i-1行和第i行我们约定这个方块是属于第i行的也就是说它凸上去了
那么要在第i行的第j列竖放一个方块的话第i-1行第j列必须没有方块
也就是说第i行的放置是受到第i-1行的限制的反过来说在第i行竖放了方块也会影响第i-1行的状态
所以这样就可以讲解一下状态转移方程了前i-2行已经放满了第i-1行的状态为ss(dp[i-1][ss])
此时在第i行开始放一些方块放的方法不定可能横放可能竖放但是按这个方案放完后
第i-1行刚好被填满且第i行的状态变为了s所以不难想到第i-1行的状态ss到第i行的状态s这个转移是唯一的
所以有 dp[i][s]sum{ dp[i-1][ss] }
最后我们详细讨论一下s和ss在什么情况下是兼容的
1.第i行的第j列为1第i-1行的第j列为1这样的话说明第i行的第j列一定不是竖放而是横放否则会与第i-1行的第j列冲突所以马上紧接着判断第i行第j1列如果是1那么满足横放的规则同时也要第i-1行第j1列也要为1否则的话这个格子没办法填充成立后向左移动两格不满足上述条件的就是两个不兼容或者不合法的状态
2.第i行第j列为1第i-1行第j列为0那么说明第i行第j列应该竖放并填充第i-1行第j列成立后向左移动一格
3.第i行第j列为0说明不放方块那么第i-1行第j列必须为1否则没法填充这个格子。若第i-1行第j列也为0不兼容不合法(至于第i行第j列这个格子空着干什么其实就是留出来给第i1行竖放的时候插进来的)那么目标状态是什么就是dp[n][maxs]maxs表示全部是1的串即第n-1行以上全部覆盖满第n行的状态为maxs即没有空着的格子也全部覆盖满了
即整个矩形全部被覆盖满了的状态最后是第1行的初始化问题因为约定了“上凸型摆放”所以第1行是不能竖放方格的只能横放方格
每横放一个必定占据两个格子所以在判断一个状态那个01串的时候连着的1的个数必定为偶数如果出现了单独的1说明不合法
*/#include cstdio
#include cstring
#define N 15
#define MAX (111)10long long dp[N][MAX];
long long ans[N][N];
int n,m;bool init(int s)
{for(int k0; km; ){if(s (1k)){if(km-1) return false;if(s(1(k1))) k2;else return false;}else k;}return true;
}bool ok(int s, int ss)
{for(int j0; jm; )if(s (1j)) //第i行第j列为1{if( ss (1j)) //第i-1行第j列也为1那么第i行必然是横放{//第i行和第i-1行的第j1都必须是1否则是非法的if( jm-1 || !(s1(j1)) || !(ss(1(j1))) ) return false;else j2;}else j; //第i-1行第j列为0说明第i行第j列是竖放}else //第i行第j列为0那么第i-1行的第j列应该是已经填充了的{if(ss(1j)) j;//已经填充else return false;}return true;
}void solve()
{int maxs;if(nm){ nn^m; mn^m; nn^m; }//交换后n是行m是列m较小那么状态数也可以相应减少maxs(1m)-1;memset(dp,0,sizeof(dp));for(int s0; smaxs; s) //枚举第一行所有可能的状态if(init(s)){dp[1][s]1; //方案数都是1//printf(%d\n,s);}for(int c2; cn; c) //按行dpfor(int s0; smaxs; s) //第i行的状态for(int ss0; ssmaxs; ss) //第i-1行的状态if(ok(s,ss))dp[c][s] dp[c-1][ss];printf(%lld\n,ans[n][m]ans[m][n]dp[n][maxs]);
}int main()
{memset(ans,-1,sizeof(ans));while(scanf(%d%d,n,m)!EOF){if(!n !m) break;if(!ans[n][m]) {printf(%lld\n,ans[n][m]);continue;}if(n1 m1) {ans[n][m]ans[m][n]0;printf(0\n);continue;}solve();}return 0;
}
