题目描述
兜兜转转,终于懂了一点
样例
//首先讲1*2化整为零,分割成一个个1*1的小方块,然后核心是先从填充横着的开始,然后填不下了再填充竖的,而且剩下的小方块的数目需要是偶数的
//这里考虑f[][],前一个括号表示状态(十进制式的二进制表示法),后一个括号表示数值.
//时间复杂度:暴力:20!(排列组合数学) . 算法优化:2^20 * 20 .
//括号里的即是十进制数,也是二进制表达式子.
//关注点放在列上
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define int long long
using namespace std;
const int N = 12,M = 1 << N;
int n,m;
int f[N][M];
bool st[M];//判断每个位置的合法状态,二进制表示,十进制储存.
vector<int> state[M];
signed main()
{
while(cin >> n >> m && n && m)
{
for(int i = 0; i < 1 << n ; i++)//用位运算符号来达到二进制表示的目的,它是以方格数目来记的.i表示的是列.
//这里之所以用n,也就是列来考虑,就是因为横砖能放的数目完全由竖边来决定.
{
int cnt = 0 ;//
bool is_valid = true;//true代表排列组方案数可行.
for(int j = 0 ; j < n ; j++)
{
if((i >> j) & 1 )//如果j这个位置是1 , 在一个宽度为1的列里面,如果往下遍历时找到了一个为1的数
{
if(cnt & 1)
{
is_valid = false; //通过 & 1 来判断这个数的奇偶性.换成%2操作也是可以的,但我估计过不了:很卡,而且慢.
break;
}
}
else cnt ++;//记录空隔子的数目.
}
if(cnt & 1) is_valid = false ;
st[i] = is_valid;
}
for(int i = 0 ; i < 1 << n ; i++)
{
state[i].clear();//排空数据防止受到之前数据的影响,而且一个一个装方便下.
for(int j = 0 ; j < 1 << n ; j++)
if((i & j) == 0 && st[i | j])state[i].push_back(j);//(i & j) == 0 表示填充的砖块不会重叠.
}
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];
/*memset(f,0,sizeof f);
f[0][0] = 1; //初始化
for(int i =1 ; i <= m ; i++)//列数:1 ~ m
for(int j = 0 ; j < 1 << n ; j++) //对应的这个的行数下可以表示的最大的横砖数目
for(int k = 0 ; k < 1 << n ; k++)
if((j & k) == 0 && st[j|k])//这里的j|k理解成位置存放关系,前面已经定义过哪些可以过,
f[i][j] += f[i-1][k];
cout << f[m][0] << endl;`*/
cout << f[m][0] << endl;
}
return 0;
}
不过代码是先自己打的,代码思路记串了,😂,思路是下一个算法的