算法核心:
利用
二进制状态压缩保存
后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;
4int 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 轨踹扪 阅读(278) |
评论 (0) |
编辑 收藏