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

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

讲解可以看lrj的蓝书

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

long long has[120][120],n,m,dp[2][1<<15],cur;//

void update(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("%lld\n",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("%lld\n",has[m][n]);

    }

    return 0;

}