首页 > 代码库 > sgu 131 - Hardwood floor

sgu 131 - Hardwood floor

题目:在m*n的地板上铺上相同的I型和L型的地板砖,问有多少种铺法。

分析:dp,组合,计数。经典dp问题,状态压缩。与zoj1100一样,只是多了几个状态。

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

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

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

                      L型的砖,因为一定会影响两层,共有4中放法,建立相邻曾关系;

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

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

           (本来准备存储状态的,不过会 MLE,所以最后一边扩展,一边加了。)

说明:只注意用%i64d,和zoj正好相反。(2011-09-28 15:47)。

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

long long F[ 10 ][ 1<<9 ];

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

int main()
{
    int n,m;
    while ( scanf("%d%d",&n,&m) != EOF && m ) {
        
        if ( m>n ) {int t = m;m = n;n = t;}
        
        int M = (1<<m)-1;
        
        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 = 0 ; j <= M ; ++ j )
            dfs( j, M, i, j );
        
        printf("%I64d\n",F[ n ][ M ]);
    }
    return 0;
}

sgu 131 - Hardwood floor