题目描述:
用1×2的多米诺骨牌,拼成4×w的矩形,总共有多少种方法?
分析:
经典题了,貌似我做过很多系列的这种题目,终于开窍了~
- #include <stdio.h>
- #include <string.h>
- #define N 100
- #define L 20
- #define clr(a) memset(a,0,sizeof(a))
- int mx[L][L];
- void print(int a[],int n){
- int i;
- for(i=0;i<n;i++) printf("%d ",a[i]);
- puts("");
- }
- int a2i(int a[]){
- int i,x=0;
- for(i=0;i<4;i++)
- x|=a[i]<<i;
- return x;
- }
- void i2a(int x,int a[]){
- int i;
- for(i=0;i<4;i++)
- a[i]=(x>>i)&1;
- }
- void fillB(int i,int a[],int k,int b[]){
- int j,r;
- if(k>=4){
- j=a2i(b);
- mx[i][j]=1;
- return;
- }
- if(a[k]==1){
- b[k]=0;
- fillB(i,a,k+1,b);
- }
- else{
- if(k<3&&a[k+1]==0){
- b[k]=b[k+1]=0;
- fillB(i,a,k+2,b);
- }
- b[k]=1;
- fillB(i,a,k+1,b);
- }
- }
- void Matrix(void){
- int i,j,k;
- int a[L],b[L];
- for(i=0;i<16;i++){
- i2a(i,a);
- fillB(i,a,0,b);
- }
- }
- int main()
- {
- int i,j,k;
- clr(mx);
- Matrix();
- //DP
- int f[N][L];
- int n=30;
- clr(f);
- f[0][0]=1;
- for(i=1;i<=n;i++){
- for(j=0;j<L-1;j++){
- f[i][j]=0;
- for(k=0;k<L-1;k++){
- if(mx[k][j])
- f[i][j]+=f[i-1][k];
- }
- }
- }
- int T,Tn;
- scanf("%d",&Tn);
- for(T=1;T<=Tn;T++){
- scanf("%d",&i);
- printf("%d %d/n",T,f[i][0]);
- }
- return 0;
- }