题解 P3272 [SCOI2011]地板

翼德天尊 · 2023-01-23 19:18:23 · 题解

给定一个 r\times c 的棋盘，用若干任意大小的 L 型砖铺满地板，求方案数。有的地方不能铺。

1\le r\times c\le 100

考虑注意到本题特殊的数据范围，其实就是限制了 \min(r,c)\le 10。于是我们 r 和 c 中将较小的一个作为轮廓线即可保证复杂度。

然后套插头 dp 一般步骤解题。

首先题目要求用 L 铺满地板，而每一个 L 都需要且只能拐一次，于是对于每一个插头，显然有三种状态：0 表示没有插头，1 表示该插头还没有拐过，2 表示该插头已经拐过了。故轮廓线用四进制数表示即可。

其次考虑转移。对于每一个格子：

• 若为障碍格，则四个插头都没有。

• 若没有左插头和上插头，则需要新建一个 L 型的砖，而由于该格本身就是一个拐点，所以右插头和下插头都为 2。

• 若左插头和上插头有其一，延伸插头即可。除此之外，如果该插头为 1，则可以选择将该格作为拐点；若该插头为 2，则可以考虑在该格停止向右向下延伸。

• 若左插头和上插头都有，则只能在两个插头都为 1 的时候合并插头。

利用 hash 表依次转移即可。

h[now].insert(0,1);
for (int i=1;i<=n;i++){
    for (int j=1;j<=m;j++){
        bool la=now;now^=1;
        h[now].clear();
        for (int k=1;k<=h[la].tot;k++){
            int p=h[la].val[k];
            ll v=h[la].sum[k];
            if (j==1){
                if ((p>>(m<<1))%4!=0) continue;
                p<<=2;
            }
            int now1=(p>>(j-1<<1))%4,now2=(p>>(j<<1))%4;
            if (!a[i][j]){
                if (!now1&&!now2) h[now].insert(p,v);
                continue;
            }
            if (!now1&&!now2){
                h[now].insert(p^(1<<(j-1<<1)),v);
                h[now].insert(p^(1<<(j<<1)),v);
                h[now].insert(p^(2<<(j-1<<1))^(2<<(j<<1)),v);
            }else if (now1&&!now2){
                h[now].insert(p^(now1<<(j-1<<1))^(now1<<(j<<1)),v);
                if (now1==1) h[now].insert(p^(1<<(j-1<<1))^(2<<(j-1<<1)),v);
                else h[now].insert(p^(now1<<(j-1<<1)),v);
            }else if (now2&&!now1){
                h[now].insert(p^(now2<<(j-1<<1))^(now2<<(j<<1)),v);
                if (now2==1) h[now].insert(p^(1<<(j<<1))^(2<<(j<<1)),v);
                else h[now].insert(p^(now2<<(j<<1)),v);
            }else if (now1&&now2){
                if (now1==1&&now2==1) h[now].insert(p^(now1<<(j-1<<1))^(now2<<(j<<1)),v);
            }
        }
    }
}