dp---轮廓线dp

---

哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级）
小乐乐搭积木
链接：https://ac.nowcoder.com/acm/contest/301/B
来源：牛客网

题目描述

小乐乐想要给自己搭建一个积木城堡。
积木城堡我们假设为n*m的平面矩形。
小乐乐现在手里有 1*2，2*1两种地砖。
小乐乐想知道自己有多少种组合方案。

输入描述:

第一行输入整数 n,m。(1<=n,m<=10)

输出描述:

输出组合方案数。

示例

输入

2 3

输出

3

ac代码

#include <iostream>
#include <string.h>
using namespace std;

int n,m;
int dp[2][(1<<11)],cur,mask;  //mask 掩码

void update(int a,int b){
    dp[cur][b] += dp[cur^1][a];  //更新状态方案数
}

int main(){
    cin>>n>>m;
    mask = (1<<m)-1; //设置掩码
    memset(dp,0,sizeof(dp));
    cur = 0; //滚动数组
    dp[cur][(1<<m)-1] = 1; //初始化
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){//当前处理位置(i,j)
            cur ^= 1; 
            memset(dp[cur],0,sizeof(dp[cur]));
            for(int k = 0;k < (1<<m);k++){//枚举当前状态

                //当前和上都放  上有空位就不能往左，也不能不放
                if(i && !(k&(1<<(m-1))))//不是第一行，且正上方为空
                {
                    update(k,((k<<1)^1)&mask);//新状态尾部置1
                }else
                {
                    //当前和左放
                    if(j && (!(k&1)))//不是第一列并且左边为空 
                        update(k,((k<<1)^3)&mask);//新状态尾两个11

                    //不放
                    update(k,(k<<1)&mask);
                                        //掩码是只取低m位作为状态
                }

            }
        }
    }
    cout<<dp[cur][(1<<m)-1]<<endl;
    return 0;
}

思路：

轮廓线dp，状压
在这道题中，假设我们有一个 5*5 的格子要填充(如图)，黑色部分不是格子的一部分，只是作为虚拟出来的"顶"。
图1中蓝色部分表示已经填充好的部分；黄色部分是状态压缩表示的状态，已经填充为1，没有为0；红色表示当前处理的位置。
图2中我们用状态01111表示当前的"轮廓"。这个状态的"头"总是在"当前"的上面，这个状态的"尾"大部分时候在"当前"的左边(图4的情况不是)。
图3中，我们"当前"的处理方式只能是填充"当前"和"头"(竖着放)，因为如果我们不这样，上方的空位就无法被填充，会被忽略过去。

轮廓线dp示意图

图4中，"当前"的左边没有格子，而且上方是0，不可能往左放，只能往上放(竖着放)。处理过之后就变成下面的新状态了。
图5种，有两种选择，往左放或者不放。
特别的，如何初始化？
处理第一行的时候，假设上面还有一层，并且都填充了(就是图中黑色部分)，这样就可以像其他位置一样处理。
怎么记录方案数？
每一个状态都是由另一个状态得到的，状态1 —>状态2 ; 状态3 —> 状态2;
可能很多状态都能到状态2，那么状态2的方案数就是 状态1方案数 + 状态2方案数 + ...
设dp[cur][state]表示cur(当前)位置为state状态的方案数。last为上一个位置。
设 k 表示处理当前位置前的状态(轮廓)，new为处理当前位置后的状态(轮廓)
转移方程有

dp[cur][new] += dp[last][k];

我先去上课 。。。。
具体实现可以看代码。
需要注意的几点：
初始化是当上面有一行不存在的，已经填充好的一行
dp[cur][(1<<m)-1] = 1
cur ^= 1 是滚动数组的操作，因为当前位置状态只和它之前位置状态有关
任何时候，上方有空位就不能选择左或者不填。