Mondriaan's Dream
题目来源:
http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10710&courseid=38
题目大意:给一个h*w(1<=h,w<=11)的矩形,用1*2的小矩形去完全覆盖此大矩形且不能重叠,问一共有多少种覆盖方法?
题目分析:此题一直在纠结着我,直到今天才把它AC。
题目的方法其实思路很简单,就是典型的状态压缩的动态规划,按行进行状态压缩,因为当前行的状态只取决于上一行的状态。每一个小的方格用1和0来表示放与不放,整个一行用一个数s来表示,第几个方格的摆放情况与s中相应的二进制位的值一一对应。
状态转移方程:设f(i,s)表示行i-1的状态为s时覆盖的方法数,则:
f(i,s)=sum{f(i+1,s’)},其中s'为第i行的状态
最终答案即为:sum{f(1,s),s为第0行状态} (h*w为偶数)
首先1*2的小矩形的摆放有两种方式:可以横着,也可以竖着。如果是横着,就对应的两位都为1;如果是竖着,当前处理这一个小方格用0表示,但下一行的相应位置必须为1,即说明如果上一行对应的位置为0,则决定了本行的对应位置只能为1;但如果是1,则本行可以为1,也可以为0;
其次,当h*w为奇数时,显然答案为0。
算法步骤:
1.首先预处理第0行的所有状态,并保存所有的合法状态于数组state[]中,这通过一个
dfs()即可完成,时间复杂度为O(w*(2^w))。
2.然后按照状态转移方程,书写DP,其中也需要按照上一行的状态来枚举当前行的状态,也 同样是用一个dfs2()就能搞定。
此题的关键在于:明白算法的思路,然后想方设法去实现即可。
附代码:
#include <iostream>
#include <memory.h>
#include <cstdio>
using namespace std;
const int maxn = 13;
typedef __int64 lld;
lld h,w;
lld state[1<<maxn],tail,head;
lld f[maxn][1<<maxn];//f(i,j)表示第i-1行的状态为j时会有f(i,j)种方法
void dfs(lld s,lld k)
{
if(k==w)
{//检查这种状态是否合理
lld i;
for(i=0;i<w;i++)
{
if((s&(1<<i))==0) continue;
else
{
if((s&(1<<(i+1)))==0) break;
else i++;
}
}
if(i>=w) {state[tail++]=s;}
return ;
}
//扩展左儿子
dfs(s,k+1);
//扩展右儿子
dfs(s|(1<<k),k+1);
}
void dfs2(lld s,lld k,lld *a,lld &t)
{
if(k==w) {a[t++]=s;return;}
for(lld i=k;i<w;i++)
{
if(s&(1<<i)) {dfs2(s,i+1,a,t);break;}
else
{
if(s&(1<<(1+i))) {dfs2(s,i+2,a,t);break;}
dfs2(s,i+1,a,t);
dfs2(s|(1<<i)|(1<<(i+1)),i+2,a,t);
break;
}
}
}
lld dp(lld row,lld s)
{
if(row==h)
{
int k;
if(s==(1<<w)-1) k=1;
else k=0;
return f[row][s]=k;
}
if(f[row][s]!=-1) return f[row][s];
lld sum=0;
lld s1=(~s)&((1<<w)-1);
lld q[1<<maxn],h=0,t=0;
dfs2(s1,0,q,t);
for(h=0;h<t;h++)
{
//cout<<q[h]<<endl;
sum+=dp(row+1,q[h]);
}
return f[row][s]=sum;
}
int main()
{
while(scanf("%I64d%I64d",&h,&w),h||w)
{
if(h*w&1) {cout<<0<<endl;continue;}
if(h==1||w==1) {cout<<1<<endl;continue;}
head=tail=0;
dfs(0,0);//预处理第一行的所有状态
lld sum=0;
memset(f,-1,sizeof(f));
for(head=0;head<tail;head++)
{
//cout<<state[head]<<endl;
sum+=dp(1,state[head]);
}
//cout<<sum<<endl;
printf("%I64d\n",sum);
}
return 0;
}
分享到:
相关推荐
状态压缩动态规划浅谈.pdf
树型动态规划和状态压缩动态规划介绍,以及经典题目讲解
树型动态规划和状态压缩动态规划.pdf
陈丹琦_基于连通性状态压缩的动态规划问题
状态压缩动态规划中的状态与时间.pdf
动态规划之状态压缩 解决一类十分让人头痛的动态规划问题
信息学发展势头迅猛,信息学奥赛的题目来源遍及各行各业,经常有一些在实际应用中很有价值的问题被...然而有一些问题却被认为很可能不存在有效的(多项式级的)算法,本文以对几个例题的剖析,简述状态压缩思想及其应用。
基于连通性状态压缩的动态规划问题.pdf
3.陈丹琦《基于连通性状态压缩的动态规划问题》3.陈丹琦《基于连通性状态压缩的动态规划问题》
动态规划是求解最优化问题的一种方法;动态规划虽然空间复杂度...另外,也收录了解决NP问题小规模求解中,优于搜索的状态压缩动态规划。 关键词:动态规划优化,四边形不等式,斜率优化,单调队列,状态压缩动态规划。
3.徐持衡《浅谈几类背包题》 8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack ...树型动态规划和状态压缩动态规划 算法导论第15章-动态规划 最长公共子序列和字符串相似度 最大矩阵连乘次数(最小连乘变形)
状态压缩类型动态规划.ppt
由湖南省雅礼中学陈丹琦写的 引入了新的概念 很容易理解 操作起来也很方便
第4章 状态压缩类动态规划-2020.06.08.pdf
状态压缩优化动态规划的详解
动态规划本来就很抽象,状态的设定和状态的转移都不好把握,而状态压缩的动态规划解决的就是那种状态很多,不容易用一般的方法表示的动态规划问题,这个就更加的难于把握了。难点在于以下几个方面:状态怎么压缩?...
算法 论文 状态压缩 动态规划 递推 hash
状态压缩类型动态规划PPT学习教案.pptx