ECNU 1029. 走道铺砖 (状压dp)

87 阅读 0 评论 58 点赞

我是靠谱客的博主明亮路人，最近开发中收集的这篇文章主要介绍ECNU 1029. 走道铺砖 (状压dp)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

单点时限: 5.0 sec

内存限制: 256 MB

有一个专门为装修设计方案的法国著名设计师。最近，他接到一个项目，为华东师大理科大楼设计走道的地砖铺设方案。此项目的委托人事先便进行了说明：地砖只有 12 一种规格，而整栋楼中同类走道又有许多个，他不想其中有任何的两个出现重复的设计方案。因此，设计师必须确定其可行性，即对一个 NM(NM 为偶数) 的走道，用 NM/2 块 1*2 的地砖将其铺满，可以有多少种不同的设计方案，如果方案总数少于此类走道的个数，则该项目不可能实现。

现在，他需要这样的一个程序，对于输入的走道规格 N、M，计算出可以设计出的不同地砖铺设方案总数。

输入格式

测试数据有多组。

每组测试数据占一行，每行有两个整数 N 和 M(1<=N,M<=11)，表示走道的长和宽。如果 N 和 M 同时为 0，表示输入结束。

输出格式

每组测试数据输出一行，每行一个整数，表示有多少种不同的铺设方案。

样例

input

output

参考：https://www.cnblogs.com/TYH-TYH/p/4899889.html

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=4005;
int N,M;
LL dp[20][3000];
void dfs(int col,int row,int state,int next)
{
if(row==M)
{
dp[col+1][next]+=dp[col][state];
return ;
}
if(((1<<row)&state)>0)
dfs(col,row+1,state,next);
if(((1<<row)&state)==0)
dfs(col,row+1,state,next|(1<<row));
if((row+1)<M&&(((1<<row)&state)==0)&&((1<<(row+1))&state)==0)
dfs(col,row+2,state,next);
}
int main()
{
while(cin>>N>>M)
{
if(N==0&&M==0)
break;
memset(dp,0,sizeof(dp));
dp[1][0]=1;
for(int i=1;i<=N;i++)
{
for(int j=0;j<(1<<M);j++)
{
if(dp[i][j])
dfs(i,0,j,0);
}
}
cout << dp[N+1][0] << endl;
}
return 0;
}