posts - 1,  comments - 0,  trackbacks - 0
算法核心:
                     利用二进制状态压缩保存后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)编辑 收藏
仅列出标题  
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿

随笔档案

搜索

  •  

最新评论