UVA 12446 How Many... in 3D! 搭积木 dp - c++编程基础

题目链接：点击打开链接

题意：

用1*1*2的方块搭出2*2*N的方块的方法数

则对于每一层有9种状态

0、全为1.

1、

0表示这个为空，__表示这两个平躺着一个方块

2、

0表示这格为空，1表示这格方块是直立放着的。

如此类推除第0种共8种状态，然后就是简单的转移。

而其他状态是无效的，不会参与到答案的计算中，所以不需要考虑

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             template 
            
              inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template 
             
               inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; const int N = 1000100; const int mod = 1000*1000*1000+7; void add(const int &y,int& x){ x += y; if(x >= mod) x-=mod; } int d[N][9]; int main() { memset(d, 0, sizeof d); d[0][0] = 1; for(int i = 0; i < N-1; i++) { add(d[i][1], d[i][0]); add(d[i][2], d[i][0]); add(d[i][4], d[i][0]); add(d[i][5], d[i][0]); add(d[i][6], d[i][0]); add(d[i][8], d[i][0]); if(i>1)add(d[i-2][0], d[i][0]); add(d[i][0], d[i+1][1]); add(d[i][0], d[i+1][3]); add(d[i][0], d[i+1][5]); add(d[i][0], d[i+1][7]); add(d[i][1], d[i+1][4]); add(d[i][2], d[i+1][4]); add(d[i][3], d[i+1][2]); add(d[i][4], d[i+1][2]); add(d[i][5], d[i+1][8]); add(d[i][6], d[i+1][8]); add(d[i][7], d[i+1][6]); add(d[i][8], d[i+1][6]); } int T, n;scanf("%d", &T); while(T--){ scanf("%d", &n); printf("%d\n", d[n][0]); } return 0; }