首页 > itarticle > uva11270 tiling dominoes（轮廓线动态规划）

uva11270 tiling dominoes（轮廓线动态规划）

admin 11月 14, 2020 0

轮廓线动态规划是一种基于状态压缩解决和连通性相关的问题的动态规划方法

这道题是轮廓线动态规划的模板

讲解可以看lrj的蓝书

代码


#include <algorithm>
#include <cstring>
using namespace std; 
long long has[120][120],n,m,dp[2][1<<15],cur;
void (int a,int b){
    if(b&(1<<m))
        dp[cur][b^(1<<m)]+=dp[cur^1][a];
}
int main(){
    memset(has,-1,sizeof(has));
    while(scanf("%d %d",&n,&m)==2){//n>=m
        if(m>n) 
            swap(m,n);
        if(has[m][n]!=-1){
            printf("%lldn",has[m][n]);
            continue;
        }
        cur=0;
        memset(dp,0,sizeof(dp));
        dp[cur][(1<<m)-1]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                cur^=1;
                memset(dp[cur],0,sizeof(dp[cur]));
                for(int k=0;k<(1<<m);k++){
                    update(k,k<<1);
                    if(i>1&&!(k&(1<<(m-1))))
                        update(k,(k<<1)^(1<<m)^1);
                    if(j>1&&!(k&1))
                        update(k,(k<<1)^2^1);
               }
            }
        has[m][n]=dp[cur][(1<<m)-1];
        printf("%lldn",has[m][n]);
    }
    return 0;
}