/*
推荐:五星
动态规划、状态压缩、dfs
题意:m*n矩形,要求使用2*1的小块矩形进行填充,共存在多少种方法。
解题思路:使用1、0对每一格进行填充,首先考虑只有两行,则存在三种情况:竖着放置第i行为1,第i+1行为0;横着放置第i行为11,第i+1行为11;第i行正好为上一行竖着放置凸出来的部分,则第i行为0,所以下面一行肯定为1。使用d[i][s]表示第i行为状态s时的最大放置方法数。状态转移方程为:d[i][a]=sum(d[i-1][b]),其中a、b必须是一个合理的组合。根据a可以使用dfs查找出所有的b,题中使用vector数组进行存储。dfs()函数中用到三个递归:
dfs(col+1,(s1<<1) | 1,(s2<<1));//情况一
dfs(col+1,(s1<<1),(s2<<1) | 1);//情况三
dfs(col+2,(s1<<2) | 3,(s2<<2) | 3);//情况二
注意:①出为初始状态,表示正好被一个小矩形填充完,则加1
另外还有,题中需要在最后一行增加一行,并且第n+1行必须为1...1这样才能保证第n行无突出情况,具体实现是输出d[m+1][(1<<n)-1]的值。不过第0行必须为0...0来保证第1行都为1,具体实现为:d[0][]的赋值,如果为d[0][0],正好被一个小矩形填充完,加1,否则情况不存在+0,等于无效。其实这道题还是有点小迷糊,主要问题:d[0][]的赋值。
*/
//#define TEST
#include <cstdio>
#include <vector>
using namespace std;
const int nMax=13;
int m,n;
long long d[nMax][1<<nMax];
vector<int> v[1<<nMax];
void dfs(int col,int s1,int s2)
{
if(col>=n)
{
if(s1<(1<<n) && s2<(1<<n))
v[s2].push_back(s1);
return;
}
dfs(col+1,(s1<<1) | 1,(s2<<1));
dfs(col+1,(s1<<1),(s2<<1) | 1);
dfs(col+2,(s1<<2) | 3,(s2<<2) | 3);
}
void dp()
{
if(m<n) swap(m,n);
for(int i=0;i<(1<<n);i++)
v[i].clear();
dfs(0,0,0);
memset(d,0,sizeof(d));
d[0][0]=1;//①
int state=1<<n;
for(int i=1;i<=m+1;i++)
for(int s=0;s<state;s++)
{
for(int j=0;j<v[s].size();j++)
{
d[i][s]+=d[i-1][v[s][j]];
#ifdef TEST
printf(":%d ",v[s][j]);
#endif
}
#ifdef TEST
printf("\n%d %d %lld\n",i,s,d[i][s]);
#endif
}
}
int main()
{
//freopen("f://data.in","r",stdin);
while(scanf("%d %d",&m,&n)!=EOF)
{
if(m==0 && n==0) break;
dp();
printf("%lld\n",d[m+1][(1<<n)-1]);
}
return 0;
}
参考博客:http://www.cppblog.com/sdfond/archive/2009/07/31/91761.html
分享到:
相关推荐
里面有非常详细的对于POJ 2411的解题报告,相信对于初学动态规划和深度优先搜索的同学来说有很好的帮助作用。
POJ水题集-----50道左右-----增加自信啊..
用Java代码实现POJ(PKU)上题2494!
很有用的解题报告。。是acm初级提高的必备资料。。。。。
北大POJ2002-Squares 解题报告+AC代码
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
East Central North America 1999。50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50...
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
Time Limit: 1000ms Memory limit: 65536kB 题目描述 有9个时钟,排成一个3*3的矩阵。 现在需要用最少的移动,将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示,每个移动会将若干个时钟的...
非常全的poj答案库 1164-1874 1000-4007
北大POJ3411-Paid Roads【class】 解题报告+AC代码
poj 1690 Your-Term-Project.md
poj 1240 Pre-Post-erous!.md
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
北大POJ1184-Smart typist【搜索与状态压缩】 解题报告+AC代码
西北工业大学-c语言-POJ-题目及答案-第七季.doc
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
poj 1028 Web Navigation 的代码,已通过!