首页 > 代码库 > zoj 1100 - Mondriaan's Dream

zoj 1100 - Mondriaan's Dream

题目:在m*n的地板上铺上相同的1*2的地板砖,问有多少种铺法。

分析:dp,组合,计数。经典dp问题,状态压缩。

            状态:设f(i,j)为前i-1行铺满,第i行铺的状态的位表示为j时的铺砖种类数;

            转移:因为只能横铺或者竖铺,那么一个砖块铺之前的状态只有两种;

                      且如果当前竖放会对下一行产生影响,建立相邻两行状态对应关系;

                      这里利用dfs找到所有f(i,j)的上一行的所有前置状态f(i-1,k)加和即可;

                      f(i,j)= sum(f(i-1,k)){ 其中,f(i-1,k)可以产生f(i,j)状态 };

           (大黄的三维DP实现简单,效率较差。)

           组合学公式 :π(4cos(pi+i/(h+1))^2+4cos(pi+j/(w+1))^2) { 1<=i<=h/2,1<=j<=w/2 }。

说明:纠结N久最后发现%I64d一直WA。%lld就过了。(2011-09-27 19:15)。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int s,l;
}seg;
seg S[ 10 ];

long long F[ 12 ][ 1<<11 ];

int  V[ 1<<11 ][ 99 ];
int  Count[ 1<<11 ];

//用dfs找到可以到达的状态 
void dfs( int A, int B, int C )
{
    if ( !A ) {
        V[ C ][ ++ Count[ C ] ] = B;
        return;
    }else {
        int V = A&-A;//取得最后一个 1的位置 
        dfs( A&~V, B&~V, C ); 
        if ( A&(V<<1) ) dfs( A&~(3*V), B, C );
    }
}

int main()
{
    int n,m;
    while ( scanf("%d%d",&n,&m) != EOF && m ) {
        
        if ( n%2&&m%2 ) {printf("0\n");continue;}
        if ( m>n ) {int t = m;m = n;n = t;}
        
        int M = (1<<m)-1;
        for ( int i = 0 ; i <= M ; ++ i ) {
            Count[ i ] = 0;
            dfs( i, M, i );
        }
        
        for ( int i = 0 ; i <= n ; ++ i )
        for ( int j = 0 ; j <= M ; ++ j )
            F[ i ][ j ] = 0LL;
        F[ 0 ][ M ] = 1LL;
            
        for ( int i = 1 ; i <= n ; ++ i )
        for ( int j = M ; j >= 0 ; -- j ) 
        for ( int k = Count[ j ] ; k >= 1 ; -- k ) 
            F[ i ][ j ] += F[ i-1 ][ V[ j ][ k ] ];
        
        printf("%lld\n",F[ n ][ M ]);
    }
    return 0;
}

zoj 1100 - Mondriaan's Dream