P3272 [SCOI2011]地板 题解

· · 题解

题目大意

给定一个网格图，使用 L 型的砖不重叠的铺满这个图，有些格子不能铺砖，问方案数。

题目分析

看到这道题，我们可以把一个 L 型砖里的所有格子看做是联通的。每个 L 砖之间互不影响，所以可以想到插头 DP。下面看看要求联通的格子的要求：

与模板题不同的是，这道题 不 要求满足限制的联通块只有一个，所以我们可以在决策过程中增加新的联通块。但是，每个连通块 只能有并且必须有 一个拐点。由这两条性质，我们可以设计出每一个插头的表示。

插头 DP 本质上是状压 DP， 不过由于要处理连通性，所以引入插头这一概念，来表示某一边界的状态，本题的插头分为 0，1，2。表示没有插头，当前的插头没有拐，当前的插头已经拐了。考虑到计算机里的位运算便捷又高效，我们把一个状态 像状压一样用一个二进制数来表示。但是要表示出 0，1，2，所以我们 用两位二进制数来表示一个插头，来实现最少需要三进制数才能实现的功能 。这是大多数插头 DP 题解和博客没有提到的关于四进制，三进制的本质。

另一个的插头 DP 的疑惑点是关于插头转移时的描述，状态表示的是 轮廓线 上的插头状态，而不是 格子 上的。m 个格子的一行，轮廓线长度为 m + 1。在处理到第 j 个格子的时候，它的左插头指的是轮廓线上第 j 个插头。上插头指的是轮廓线上第 j + 1 个插头。这个格子转移完，将轮廓线翻下来，他的下插头是轮廓线上第 j 个插头，右插头是轮廓线上第 j + 1 个插头。这是状态转移的关键，请结合其他博客的图理解我说的话。

下面分类讨论状态的转移。

对于当前正在决策的这个格子：

更新状态的时候，记得想着轮廓线，是否要删掉原先的插头，以及怎么添加新插头。

由于我们是逐行考虑去枚举每一格，所以如果列比行大，在这题的数据范围下会超时，我们在输入的时候预处理一下即可。

code :

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int Mod = 20110520;
const int N = 20;
const int M = 300010;

int n, m, ans;
int a[150][150];
char s;
int que[2][M], val[2][M];
int tw[N], cnt[2];
int ei, ej;
int now;
int last, num;

int Next[M * 10], head[M * 10];
int idx;
void Zip(int bit, int num){
    long long u = bit % Mod + 1;
    for(int i = head[u]; i; i = Next[i]){
        if(que[now][i] == bit){
            val[now][i] = (val[now][i] + num) % Mod;
            return;
        }
    }
    Next[++ cnt[now]] = head[u];
    head[u] = cnt[now];
    que[now][cnt[now]] = bit;
    val[now][cnt[now]] = num % Mod;
}

void dp(){
    cnt[now] = 1;
    val[now][1] = 1;
    que[now][1] = 0;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= cnt[now]; ++ j) que[now][j] <<= 2;
        for(int j = 1; j <= m; ++ j){
            memset(head, 0, sizeof head);
            last = now; now ^= 1;
            cnt[now] = 0;
            for(int k = 1; k <= cnt[last]; ++ k){
                int bit = que[last][k], num = val[last][k];
                int b1 = (bit >> ((j - 1) * 2)) % 4, b2 = (bit >> (j * 2)) % 4;
                if(!a[i][j]){
                    if(!b1 && !b2) Zip(bit, num);
                }

                else if(!b1 && !b2){
                    if(a[i + 1][j] && a[i][j + 1]) Zip(bit + tw[j - 1] * 2 + tw[j] * 2, num);
                    if(a[i + 1][j]) Zip(bit + tw[j - 1], num);
                    if(a[i][j + 1]) Zip(bit + tw[j], num); 
                }

                else if(b1 && !b2){
                    if(b1 == 1){
                        if(a[i][j + 1]) Zip(bit - tw[j - 1] + tw[j], num);
                        if(a[i + 1][j]) Zip(bit + tw[j - 1], num);
                    }
                    if(b1 == 2){
                        if(a[i][j + 1]) Zip(bit - tw[j - 1] * 2 + tw[j] * 2, num); 
                        Zip(bit - tw[j - 1] * 2, num); // 结束
                        if(i == ei && j == ej) ans = (ans + num) % Mod;
                    }
                }

                else if(!b1 && b2) {
                    if(b2 == 1){
                        if(a[i + 1][j]) Zip(bit - tw[j] + tw[j - 1], num);
                        if(a[i][j + 1]) Zip(bit + tw[j], num);
                    }
                    if(b2 == 2){
                        if(a[i + 1][j]) Zip(bit - tw[j] * 2 + tw[j - 1] * 2, num);
                        Zip(bit - tw[j] * 2, num); // 结束 
                        if(i == ei && j == ej) ans = (ans + num) % Mod;
                    }
                }

                else if(b1 == 1 && b2 == 1){
                    if(i == ei &&  j == ej) ans = (ans + num) % Mod; 
                    Zip(bit - tw[j - 1] - tw[j], num);
                }
            }
        }
    }
}

signed main(){
    scanf("%d%d", &n, &m);
    if(n>=m){
        for(int i = 1; i <= n; ++ i){
            for(int j = 1; j <= m; ++ j){
                char ch = getchar();
                while(ch != '*' && ch != '_') ch = getchar();
                a[i][j] = (ch == '_');
                if(a[i][j]) ei = i, ej = j;
            }
        }
    }
    else{
        swap(n, m);
        for(int i = m; i > 0; -- i){
            for(int j = 1;j <= n; ++ j){
                char ch = getchar();
                while(ch != '*' && ch != '_') ch = getchar();
                a[j][i] = (ch == '_');
                if(a[j][i] && ((j > ei) || (j == ei && i > ej))) ei = j, ej = i;
            }
        }
    }
    tw[0] = 1;
    for(int i = 1; i <= 11; ++ i) tw[i] = tw[i - 1] << 2;
    dp();
    printf("%lld\n", ans);
    return 0;
}