| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 16061 | Accepted: 9297 |
Description
Input
Output
For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.Sample Input
1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0
Sample Output
1 0 1 2 3 5 144 51205
Source
动规 状压DP
这居然是状压DP……刚看题的时候满满都是插头DP的既视感 （后来知道插头DP也能做）
用01串代表一整行的状态，0表示格子暂时为空，1表示填满
转移时判断上一行状态和当前状态的每一位：
0 1
0 两格都为空，显然不行 0 可行，上一行填满，这一行留空等着放竖的
0 1
1 可行，上0下1表示一个竖块 1 如果下一列也是11，这代表两行各有一块横放。否则冲突，不可行
↑只有四个状态判断，多么简单（沙茶的我才用了足足一小时就想出来啦）
然后跑了900ms愉快垫底
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #define LL long long 7 using namespace std; 8 const int mxn=1<<13; 9 LL f[2][mxn]; 10 int now,pre; 11 int n,m; 12 bool check(int p,int r){ 13 // printf("p:%d r:%d\n",p,r); 14 int tmp=1; 15 for(int i=0;i<m;i++){ 16 int x=p&tmp;int y=r&tmp; 17 if(!x && !y)return 0; 18 if((x && !y)||(!x && y)); 19 else if(x && y){ 20 tmp<<=1; 21 x=p&tmp;y=r&tmp; 22 if(x && y){i++;tmp<<=1;continue;} 23 else return 0; 24 } 25 tmp<<=1; 26 } 27 return 1; 28 } 29 int main(){ 30 int i,j; 31 while(scanf("%d%d",&n,&m) && n && m){ 32 if(n*m%2){ printf("%d\n",0);continue;} 33 if(n<m)swap(n,m); 34 int ed=(1<<(m))-1; 35 now=0,pre=1; 36 memset(f,0,sizeof f); 37 for(i=0;i<=ed;i++){ if(check(ed,i))f[now][i]=1; } 38 for(i=2;i<=n;i++){ 39 swap(now,pre); 40 memset(f[now],0,sizeof f[now]); 41 for(j=0;j<=ed;j++){ 42 for(int k=0;k<=ed;k++){ 43 if(check(k,j))f[now][j]+=f[pre][k]; 44 } 45 } 46 } 47 printf("%lld\n",f[now][ed]); 48 } 49 return 0; 50 }
每次状压写出来都跑的特别慢，我的常数可能是假的
之后看了别人的题解，发现可以根据上述转移推出更多性质而快速判定
比如说这样 （45、46行） 100ms
再深一步，用DFS预处理状态，可以优化到0ms，不过懒得写了233
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #define LL long long 7 using namespace std; 8 const int mxn=1<<11; 9 LL f[2][mxn]; 10 bool ok[mxn]; 11 int now,pre; 12 int n,m; 13 bool check(int p,int r){ 14 // printf("p:%d r:%d\n",p,r); 15 int tmp=1; 16 for(int i=0;i<m;i++){ 17 int x=p&tmp;int y=r&tmp; 18 if(!x && !y)return 0; 19 if((x && !y)||(!x && y)); 20 else if(x && y){ 21 tmp<<=1; 22 x=p&tmp;y=r&tmp; 23 if(x && y){i++;tmp<<=1;continue;} 24 else return 0; 25 } 26 tmp<<=1; 27 } 28 return 1; 29 } 30 int main(){ 31 int i,j; 32 while(scanf("%d%d",&n,&m) && n && m){ 33 if(n*m%2){ printf("%d\n",0);continue;} 34 if(n<m)swap(n,m); 35 int ed=(1<<(m))-1; 36 now=0,pre=1; 37 memset(ok,0,sizeof ok); 38 memset(f,0,sizeof f); 39 for(i=0;i<=ed;i++){ if(check(ed,i))f[now][i]=1,ok[i]=1; } 40 for(i=2;i<=n;i++){ 41 swap(now,pre); 42 memset(f[now],0,sizeof f[now]); 43 for(j=0;j<=ed;j++){ 44 for(int k=0;k<=ed;k++){ 45 if((k|j)!=(1<<m)-1)continue; 46 if(!ok[k&j])continue; 47 if(check(k,j))f[now][j]+=f[pre][k]; 48 } 49 } 50 } 51 printf("%lld\n",f[now][ed]); 52 } 53 return 0; 54 }
原文：http://www.cnblogs.com/SilverNebula/p/6429283.html
