首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。