算法核心：
利用
二进制状态压缩保存
后n个格子是否放置，利用位运算可以更高效率地状态转移（在本程序中，第i位二进制保存：后n个格子中，在第i列的格子是否已填）。由于可以由前一个格子状态转移，利用滚动数组节省空间。
具体算法：
1、由于每个格子都要填满，所以穷举每个格子。
2、每个格子的状态可以由前一个格子的状态转移得到
a,如果前一个格子某状态中当前格子已填，直接加在当前格子的相应的状态中。
b,如果前一个格子某状态中当前格子未填，加在竖放的状态中。
c,如果前一个格子某状态中当前格子未填，下一个格子未放，且不是最后一列，加在横放的状态中
1
#include<cstdio>
2#include<string.h>
3long long f[2][4100],a,b,n,m,k,j,p;
4
int main()
{
5
while(scanf("%d%d",&n,&m),memset(f,0,sizeof(f)),f[0][0]=p=1,a=n>m?n:m,b=n+m-a){
6
while(a--)
7 for(j=0;++j<=b;memset(f[p=1-p],0,sizeof(f[p])))
8 for(k=(1<<b);--k+1;)
9 if(k&1<<j-1)
10 f[p][k&~(1<<j-1)]+=f[1-p][k]; //不做变动
11 else{
12 f[p][k|1<<j-1]+=f[1-p][k]; //放置一个竖向方块
13 if(j<b&&!(k&1<<j))
14 f[p][k|1<<j]+=f[1-p][k]; //放置一个横向方块
15
}
16 printf("%lld\n",f[1-p][0]);
17 }
18
}
19
PS:本题也有数学方法。不认为数学方法，很有技术含量、能比这算法更好。虽然我不会。（看到三角函数我就确定我不会了）
posted @
2011-04-10 22:39 轨踹扪 阅读(270) |
评论 (0) |
编辑 收藏