Mondriaan's Dream - POJ 2411(状态压缩)

题目大意:有一些1*2的矩形,现在用这些小矩形覆盖M*N的大矩形,不能重复覆盖,并且要覆盖完全,求有多少种覆盖方式。

分析:可以使用1和0两种状态来表示这个位置有没有放置,1表示放置,0表示没有放置,可以有三种放置方式。

一,竖着放。 二,不放。三,横着放。直接DFS这些情况就行了................还是递归容易理解。

代码如下:

=========================================================================================================

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std; const int MAXN = ;
const int Bit = ; long long dp[MAXN][<<Bit];
int M, N; void DFS(int row, int col, int now, int pre)
{
if(col == N)
{
dp[row][now] += dp[row-][pre];
return ;
} if(col+ <= N)
{
DFS(row, col+, now<<|, pre<<);///这一位竖着放
DFS(row, col+, now<<, pre<<|);///这一位不放
}
if(col+ <= N)
DFS(row, col+, now<<|, pre<<|);
} int main()
{
while(scanf("%d%d", &M, &N) != EOF && M+N)
{
memset(dp, , sizeof(dp));
if(N > M)swap(N, M); dp[][(<<N)-] = ; for(int i=; i<=M; i++)
DFS(i, , , ); printf("%lld\n", dp[M][(<<N)-]);
} return ;
}
上一篇:android设计模式—命令设计模式


下一篇:【python基础】文件操作