ZJU2994 Tiling a Grid With Dominoes - 動态規劃 變換矩陣

題目描述：

用1×2的多米諾骨牌，拼成4×w的矩形，總共有多少種方法？

分析：

經典題了，貌似我做過很多系列的這種題目，終于開竅了~

1. #include <stdio.h>
2. #include <string.h>
3. #define N 100
4. #define L 20
5. #define clr(a) memset(a,0,sizeof(a))
6. int mx[L][L];
7. void print(int a[],int n){
8.     int i;
9.     for(i=0;i<n;i++) printf("%d ",a[i]);
10.     puts("");
11. }
12. int a2i(int a[]){
13.     int i,x=0;
14.     for(i=0;i<4;i++)
15.         x|=a[i]<<i;
16.     return x;
17. }
18. void i2a(int x,int a[]){   
19.     int i;
20.     for(i=0;i<4;i++)
21.         a[i]=(x>>i)&1;
22. }
23. void fillB(int i,int a[],int k,int b[]){
24.     int j,r;
25.     if(k>=4){
26.         j=a2i(b);
27.         mx[i][j]=1;
28.         return;
29.     }
30.     if(a[k]==1){
31.         b[k]=0;
32.         fillB(i,a,k+1,b);
33.     }
34.     else{
35.         if(k<3&&a[k+1]==0){
36.             b[k]=b[k+1]=0;
37.             fillB(i,a,k+2,b);
38.         }
39.         b[k]=1;
40.         fillB(i,a,k+1,b);
41.     }
42. }
43. void Matrix(void){
44.     int i,j,k;
45.     int a[L],b[L];
46.     for(i=0;i<16;i++){
47.         i2a(i,a);
48.         fillB(i,a,0,b);
49.     }
50. }
51. int main()
52. {
53.     int i,j,k;
54.     clr(mx);
55.     Matrix();
56.     //DP
57.     int f[N][L];
58.     int n=30;
59.     clr(f);
60.     f[0][0]=1;
61.     for(i=1;i<=n;i++){
62.         for(j=0;j<L-1;j++){
63.             f[i][j]=0;
64.             for(k=0;k<L-1;k++){
65.                 if(mx[k][j])
66.                 f[i][j]+=f[i-1][k];
67.             }
68.         }
69.     }
70.     int T,Tn;
71.     scanf("%d",&Tn);
72.     for(T=1;T<=Tn;T++){
73.         scanf("%d",&i);
74.         printf("%d %d/n",T,f[i][0]);
75.     }    
76.     return 0;
77. }