哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级）
小乐乐搭积木
链接：https://ac.nowcoder.com/acm/contest/301/B
来源：牛客网
题目描述
小乐乐想要给自己搭建一个积木城堡。
积木城堡我们假设为n*m的平面矩形。
小乐乐现在手里有 1*2，2*1两种地砖。
小乐乐想知道自己有多少种组合方案。
输入描述:
第一行输入整数 n,m。(1<=n,m<=10)
输出描述:
输出组合方案数。
示例
输入
2 3
输出
3
ac代码
#include <iostream>
#include <string.h>
using namespace std;
int n,m;
int dp[2][(1<<11)],cur,mask; //mask 掩码
void update(int a,int b){
dp[cur][b] += dp[cur^1][a]; //更新状态方案数
}
int main(){
cin>>n>>m;
mask = (1<<m)-1; //设置掩码
memset(dp,0,sizeof(dp));
cur = 0; //滚动数组
dp[cur][(1<<m)-1] = 1; //初始化
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){//当前处理位置(i,j)
cur ^= 1;
memset(dp[cur],0,sizeof(dp[cur]));
for(int k = 0;k < (1<<m);k++){//枚举当前状态
//当前和上都放 上有空位就不能往左，也不能不放
if(i && !(k&(1<<(m-1))))//不是第一行，且正上方为空
{
update(k,((k<<1)^1)&mask);//新状态尾部置1
}else
{
//当前和左放
if(j && (!(k&1)))//不是第一列并且左边为空
update(k,((k<<1)^3)&mask);//新状态尾两个11
//不放
update(k,(k<<1)&mask);
//掩码是只取低m位作为状态
}
}
}
}
cout<<dp[cur][(1<<m)-1]<<endl;
return 0;
}
思路：
轮廓线dp，状压
在这道题中，假设我们有一个 5*5 的格子要填充(如图)，黑色部分不是格子的一部分，只是作为虚拟出来的"顶"。
图1中蓝色部分表示已经填充好的部分；黄色部分是状态压缩表示的状态，已经填充为1，没有为0；红色表示当前处理的位置。
图2中我们用状态01111表示当前的"轮廓"。这个状态的"头"总是在"当前"的上面，这个状态的"尾"大部分时候在"当前"的左边(图4的情况不是)。
图3中，我们"当前"的处理方式只能是填充"当前"和"头"(竖着放)，因为如果我们不这样，上方的空位就无法被填充，会被忽略过去。
轮廓线dp示意图
图4中，"当前"的左边没有格子，而且上方是0，不可能往左放，只能往上放(竖着放)。处理过之后就变成下面的新状态了。
图5种，有两种选择，往左放或者不放。
特别的，如何初始化？
处理第一行的时候，假设上面还有一层，并且都填充了(就是图中黑色部分)，这样就可以像其他位置一样处理。
怎么记录方案数？
每一个状态都是由另一个状态得到的，状态1 —>状态2 ; 状态3 —> 状态2;
可能很多状态都能到状态2，那么状态2的方案数就是 状态1方案数 + 状态2方案数 + ...
设dp[cur][state]表示cur(当前)位置为state状态的方案数。last为上一个位置。
设 k 表示处理当前位置前的状态(轮廓)，new为处理当前位置后的状态(轮廓)
转移方程有
dp[cur][new] += dp[last][k];
我先去上课 。。。。
具体实现可以看代码。
需要注意的几点：
初始化是当上面有一行不存在的，已经填充好的一行
dp[cur][(1<<m)-1] = 1
cur ^= 1 是滚动数组的操作，因为当前位置状态只和它之前位置状态有关
任何时候，上方有空位就不能选择左或者不填。
网友评论