poj2411

发表于 | 分类于 | 阅读数 次

链接:poj2411

题解

  • dp[i][j]表示前i行都合法放置的情况下第i行方法为j的方案数
  • 这里我们规定当前这位如果不放,那么该位为0,
  • 当前这位如果右放,对应两位为1
  • 如果下放,当前位为0,下一行的对应位为1
  • 由于要求完美覆盖,我们可以预处理出所有合法放置及关系,然后一个简单状压dp就解决了(不预处理也能AC)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=15;
    const int M=1<<11;
    int n,m,path[M*M+7][2],cnt;
    ll dp[N][M];
    inline void get(int a,int pre,int now){
    	if(a>m)return ;
    	if(a==m){
    		path[++cnt][0]=pre;
    		path[cnt][1]=now;
    	}
    	get(a+1,pre<<1|1,now<<1);    //不放
    	get(a+1,pre<<1,now<<1|1);	 //上方
    	get(a+2,pre<<2|3,now<<2|3);  //右放
    }

    int main(){
    	while(~scanf("%d%d",&n,&m)&&(n||m)){
    		cnt=0;
    		get(0,0,0);
    		memset(dp,0,sizeof dp);
    		dp[0][(1<<m)-1]=1;
    		rep(i,1,n)rep(j,1,cnt)dp[i][path[j][1]]+=dp[i-1][path[j][0]];
    		printf("%lld\n",dp[n][(1<<m)-1]);
    	}
    	return 0;
    }