poj2411二进制压缩滚动dp，16ms——打表又能如何？

轨踹扪 — Sun, 10 Apr 2011 14:39:00 GMT

算法核心：
                     利用二进制状态压缩保存后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:本题也有数学方法。不认为数学方法，很有技术含量、能比这算法更好。虽然我不会。（看到三角函数我就确定我不会了）

轨踹扪 2011-04-10 22:39 发表评论

C++博客-kill-myself

poj2411二进制压缩滚动dp，16ms——打表又能如何？