kirito
文章 标签 分类 友链 关于
kirito

轮廓线dp

 收录于  类别 algorithm
     约 1394 字   预计阅读 3 分钟    次阅读     条评论  

哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级）

小乐乐搭积木

链接：https://ac.nowcoder.com/acm/contest/301/B

来源：牛客网

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

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

输出组合方案数。

输入

2 3

输出

3

 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
38
39
40
41
42
43
44

#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中，我们"当前"的处理方式只能是填充"当前"和"头"(竖着放)，因为如果我们不这样，上方的空位就无法被填充，会被忽略过去。

https://blog-1256556944.file.myqcloud.com/public/contour-dp.png

图4中，“当前"的左边没有格子，而且上方是0，不可能往左放，只能往上放(竖着放)。处理过之后就变成下面的新状态了。

图5中，有两种选择，往左放或者不放。

特别的，如何初始化？

处理第一行的时候，假设上面还有一层，并且都填充了(就是图中黑色部分)，这样就可以像其他位置一样处理。

怎么记录方案数？

每一个状态都是由另一个状态得到的，状态1 —>状态2 ; 状态3 —> 状态2; 可能很多状态都能到状态2，那么状态2的方案数就是： 状态1方案数 + 状态2方案数 + …

设dp[cur][state]表示cur(当前)位置为state状态的方案数。last为上一个位置。

设 k 表示处理当前位置前的状态(轮廓)，new为处理当前位置后的状态(轮廓)

转移方程有

1

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

我先去上课 。。。。

具体实现可以看代码。

需要注意的几点：

初始化是当上面有一行不存在的，已经填充好的一行

dp[cur][(1<<m)-1] = 1

cur ^= 1 是滚动数组的操作，因为当前位置状态只和它之前位置状态有关

任何时候，上方有空位就不能选择左或者不填。

更新于 2018-12-06
 algorithm, dp
返回 | 主页