题解：P5056 【模板】插头 DP

a_small_OIer · 2026-05-18 21:45:50 · 题解

题外话：听了机房 dalao 长达一晚上的讲解，终于写出来了……

P5056 【模板】插头 DP

前置知识

• 轮廓线 DP （如果你不会可以参考 P10975 Mondriaan's Dream / 蒙德里安的梦想）

• 本题（或许可以称为弱化版？）弱化版：P5074 Eat the Trees，建议通过 P5074 后再来挑战本题。

• 推荐阅读：陈丹琦《基于连通性状态压缩的动态规划问题》

题意

给出 n\times m 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？

解法

插头 DP。

（默认你已经通过了 P5074）

:::info[一些图例解释]

• 黄色区域为已经计算的区域；
• 紫色为正在遍历的位置；
• 轮廓线为黄色和白色的交界处；
• 粗体箭头指从一种状态转移到另一种状态；
• 没有特殊说明默认省略图中已经计算区域的路线。 :::

状态设计

我们认为以下两种状态是等价的：

显然，已经计算的区域内的路径是不重要的，所以我们认定这两种状态是等价的（指转移方程全部相同）。

很明显，本题与 P5074 的区别的是 P5074 只有 0,1 两中状态，但是本题有进、出、不存在边三种状态，那我们只需要一个三进制数存状态就好啦……

真的好了吗？三进制数的实现是非常麻烦的，而且常数也没有很优，所以我们考虑使用四进制数存储轮廓线的状态：

转移设计

通过枚举我们发现存在以下几种状态的转移：

• 如果正在遍历的位置状态是障碍，跳过就好啦。

• 如果正在遍历的位置状态是一个 1、一个 2，那么全部变成 0 即可：

  如图，直接抛弃紫色方格上的两个箭头即可。

• 如果正在遍历的位置状态都是 1 或 2，那么全部变成 0，再将其他一个位置的状态变为相反的 1 或 2，保证存在回路，如下二图。

• 如果正在遍历的位置状态是仅剩的一个 1 和一个 2，如图：

  • 如果在最后一个非障碍的格子出现：将状态变成 0 计算答案即可；
  • 如果不在最后一个非障碍的格子出现：很明显这是一个非法的状态，不需要考虑这个情况的转移。

最终答案 ans = dp_{n,m,0}。

一个 tips：四进制数的运算非常麻烦，建议解压成十进制后再计算。

AC code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//十年OI一场空，不开long long见祖宗
int n , m , ex , ey;
char s[15][15];
int flag[15][15];
map<int , LL> dp , pre;
int num[20] , mx;
inline void decode(int x){//解码
    for(int i = 0 ; i <= m ; ++i)
        num[i] = 0;
    int c = 0;
    while(x){
        num[m - c] = x & 3;
        x >>= 2;
        c += 1;
    }
}
int encode(){//编码
    int res = 0;
    for(int i = 0 ; i < mx ; ++i)
        res = (res << 2) + num[i];
    return res;
}
int main(){
    //freopen(".in" , "r" , stdin);
    //freopen(".out" , "w" , stdout);
    scanf("%d%d" , &n , &m);
    for(int i = 0 ; i < n ; ++i)
        scanf("%s" , s[i]);
    ex = 0 , ey = 1;//最后的不是障碍的位置
    for(int i = 0 ; i < n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(s[i][j - 1] == '.'){
                flag[i][j] = 1;
                ex = i , ey = j;
            }
    mx = m + 1;
    dp[0] = 1;
    for(int i = 0 ; i < n ; ++i){
        for(int j = 0 ; j <= m ; ++j){
            if(i == ex && j == ey){
                printf("%lld\n" , dp[0]);
                return 0;
            }
            swap(pre , dp);
            dp.clear();
            for(auto k : pre){
                LL v = k.second;
                decode(k.first);
                if(j == m){
                    if(num[j] == 0)
                        dp[k.first >> 2] += v;
                    continue;
                }
                int a = num[j] , b = num[j + 1];
                if(flag[i][j + 1] == 0){
                    if(a == 0 && b == 0)
                        dp[k.first] += v;
                    continue;
                }
                if(a == 0 && b == 0){
                    num[j] = 1 , num[j + 1] = 2;
                    dp[encode()] += v;
                }
                if(a == 1 && b == 2 && i == ex && j + 1 == ey){
                    num[j] = 0 , num[j + 1] = 0;
                    dp[encode()] += v;
                }
                if(a == 1 && b == 1){
                    num[j] = num[j + 1] = 0;
                    int f = 0 , c1 = 1;
                    for(int l = j + 2 ; l <= m ; ++l){
                        if(num[l] == 1)
                            c1 += 1;
                        if(num[l] == 2){
                            c1 -= 1;
                            if(c1 == 0){
                                num[l] = 1;
                                f = 1;
                                break;
                            }
                        }
                    }
                    if(f)
                        dp[encode()] += v;
                }
                if(a == 2 && b == 2){
                    num[j] = num[j + 1] = 0;
                    int f = 0 , c2 = 1;
                    for(int l = j - 1 ; l >= 0 ; --l){
                        if(num[l] == 2)
                            c2 += 1;
                        if(num[l] == 1){
                            c2 -= 1;
                            if(c2 == 0){
                                num[l] = 2;
                                f = 1;
                                break;
                            }
                        }
                    }
                    if(f)
                        dp[encode()] += v;
                }
                if(a == 0 && b == 1){
                    dp[k.first] += v;
                    num[j] = 1 , num[j + 1] = 0;
                    dp[encode()] += v;
                }
                if(a == 1 && b == 0){
                    dp[k.first] += v;
                    num[j] = 0 , num[j + 1] = 1;
                    dp[encode()] += v;
                }
                if(a == 0 && b == 2){
                    dp[k.first] += v;
                    num[j] = 2 , num[j + 1] = 0;
                    dp[encode()] += v;
                }
                if(a == 2 && b == 0){
                    dp[k.first] += v;
                    num[j] = 0 , num[j + 1] = 2;
                    dp[encode()] += v;
                }
                if(a == 2 && b == 1){
                    num[j] = 0 , num[j + 1] = 0;
                    dp[encode()] += v;
                }
            }
        }
    }
    return 0;
}

好啦，现在你已经通过此题啦，来做做双倍经验吧：B4299 [蓝桥杯青少年组国赛 2022] 路线。

入门题库的题一定要能入门啊。