【算法】插头 Dp 入门 -boshi

于由boshi发布

插头 Dp


接水管问题

​ 两个黑色格子内应该填入什么方块才能使两路水管联通呢？这显然是一个” 胎教+幼儿园-“ 的题目 (参照洛谷的评级方式)，但是将其应用到 Dp 上问题或许会变得较为复杂。

​ 比如我们能否用蓝色的水管铺成若干回路，占满一个 n*m 的平面？下面我们将着重讨论这类问题。

平面布线问题

​ 对于以下的两幅图，如果用 3 条电线将相同颜色的点连在一起，且电线只能分布在直线的一侧，不可相互交叉，两幅图都存在合法的链接方案吗？

​ 显然，第一幅图存在唯一的一种链接方式，而第二幅图没有。至于为什么，我们可以结合括号序列分析。

​ 从左往右读这个序列，当我们看见一个左括号，我们会从这里连出一根相应颜色的电线，把这条电线连接到对应的右括号上，于是平面被划分为了两部分：电线内和电线外。不能存在跨越两个部分的电线。

​ 在这一对括号之间的所有括号都对应的是电线内的平面，于是这些括号不能跟电线外的括号配对。所以像之前的第二种括号序列是不合法的，对应的连线方式也是不存在的。

​ 这就是插头 Dp 的思想的一部分：将复杂的接线方式一一映射成一个合法括号序列。

​ 当然，每一个合法的括号序列也对应着一个合法的接线方式。比如第二种情况虽然是不合法的，但是其括号序列不考虑颜色却是合法的，它对应的合法的接线情况也是唯一存在的。

插头 Dp

例 1 (Eat the Trees , HDU1693)：

​ 给定一个 N*M 的方格平面，从某个方格出发，沿 4 联通的方格遍历若干没有访问过的方格，最终形成一个回路。问：能否用若干个回路不重复地覆盖整个平面？

分析：

​ 根据接水管问题，我们可以想出这样一种方式模拟遍历的过程。用如下的几种方块铺满整个平面，且方块上的线条形成若干回路。

平面布线

​ 假设你的弟弟已经帮你铺完了前 x 行，并且他可以保证之前的方块都非常合理的相互连接，现在第 x 行大概会是这样的：

平面布线

​ 那么，我们只需要保证接下来铺的方块和第 x 行的方块相互连接，且自相连接就行了，我们就不需要再去管之前的方块是怎么铺的了。于是，我们将整个体系庞大的状态就可以转换成每一行的状态相互连接而成的。

​ 更进一步，我们甚至不需要一次转移一行的状态，我们只需要每次多铺一个方块，在相邻方块之间转移就行了。比如：

平面布线

​ 所以我们只需要记录当前这个轮廓线的状态，枚举下一个位置放什么方块，就可以在相邻状态之间转移了。

状态转移：

​ 根据上面的分析，我们尝试用 $f[i][j][S]$表示：是否存在一种铺方块的方式使下一个要铺第 i 行第 j 列的方块时，当前轮廓线的状态是二进制数 S. 需要注意的是，由于我们的轮廓线长度为 m+1, 所以这个二进制数 S 也是 m+1 位的。如果 S 的某一位为 1，则代表这里有一个伸出来的水管，我们称作一个 “插头”。

​ 然后根据轮廓线在铺方块位置的状态，我们选择合适的方块铺在那里，转移到铺完后的状态。这样子非常好想，代码比较码农，但是写起来很爽。

​ 转移大致分为几种：1. 合并两个插头。2. 延续一个插头。3. 新建连个插头 (一个 L 形的方块)。

平面布线

例 2 (Tony’s Tour , POJ1739)：

​ 给定一个 N*M 的方格平面，方格中存在一些不能经过的障碍，是否存在一个回路遍历整个平面？

分析：

​ 由于这次是一个回路。如果我们像上一题一样一顿乱转移，是会出问题的。因为上一题是 “若干个环”，而这一题只允许存在一个环。所以我们有必要引入之前提到的括号序列使状态的描述更清晰。

​ 对于在之前已经连接在一起的一对插头，我们用一对括号表示。在转移过程中，我们绝不能合并一对括号，因为这样会形成一个新的环。只有在最后一次转移时，我们才能将当前唯一一个环封闭，大功告成。由于状态变为了一个 3 进制数，我们不妨用 4 进制代替它以方便位运算。

​ 同样，状态转移十分码农 (分 9 类讨论)，合并插头是需要考虑合并的两个插头分别为什么括号。

平面布线

例 3：地图 (DGKOI2016DAY1)：

​ 题意是：给出一个 $n\times m$的地图 ($n,m\leq 7$). 地图上存在已知的”S”，”X”，”E”，”#”，”.”，还有未知的点。一个合法的地图满足”S”，”X”，”E” 有且仅有一个且两两通过”.” 或自身连通。如果未知的点可以改成任何一种符号，求所有可能的合法地图的总数。

分析：

​ 同样是插头 dp，只是维护的东西变了。现在我们需要维护格子的连通性。

​ 我们先想想轮廓线如何设置。这个轮廓线一定需要保存有关当前联通块的信息。给每个联通块赋予一个数字，如果用数字表示当前方格属于哪个联通块，我们就可以将当前状态压缩成一个数。由于每一行最多有 4 个还没封闭的联通块，和一种障碍，所以一个 5 进制数似乎就足够了。我采用的是 0=障碍，1 以上=联通块。

​ 这样会存在一种问题：0102 和 0201 实际上属于一种状态，但是表示方法却不同。因此我们需要将这个数字用最小表示法表示。

​ 接着考虑三个特殊点的状态。可以用三个数分别表示三个特殊点所属的联通块。特殊点有可能属于一个联通块，也有可能还没有出现。也有可能存在于一个闭合的联通块中。

  • 当数字为 0 时说明这个点还没有出现在轮廓线上方。
  • 数字为轮廓线上存在的数字时说明这个点属于这个数字对应的联通块。
  • 数字为轮廓线上不存在的非 0 数字时说明这个点属于一个已经闭合的联通块中。

​ 然后搞清楚细节和具体实现后就可以 DP 了。

9

代码：

Eat the Trees(HDU1693)

​ 这道题的方格平面上是存在障碍格的，要求用若干回路不重叠覆盖整个平面。

#include <iostream>
#include <cstring>
#include <cstdio>
#define mov(x) (1<<(x))
#define MX 13

using namespace std;

typedef long long ll;

int mp[MX][MX];
int n, m;
ll f[MX][MX][mov(MX)];

void input()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            scanf("%d", &mp[i][j]);
    for(int i=0; i<=n+1; i++)mp[i][0]=mp[i][m+1]=0;
    for(int i=0; i<=m+1; i++)mp[0][i]=mp[n+1][i]=0;
}

ll work()
{
    f[1][0][0]=1;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<m; j++)
        {
            for(int k=0; k<mov(m+1); k++)
            {
                if(mp[i][j+1])
                {
                    if(mp[i][j+2]&& mp[i+1][j+1]&& !(k&mov(j))&& !(k&mov(j+1))) f[i][j+1][(k|mov(j))|mov(j+1)]+=f[i][j][k];
                    if(mp[i+1][j+1]&& (k&mov(j))&& !(k&mov(j+1))) f[i][j+1][k]+=f[i][j][k];
                    if(mp[i][j+2]&& (k&mov(j))&& !(k&mov(j+1))) f[i][j+1][(k^mov(j))|mov(j+1)]+=f[i][j][k];
                    if(mp[i+1][j+1]&& !(k&mov(j))&& (k&mov(j+1))) f[i][j+1][(k|mov(j))^mov(j+1)]+=f[i][j][k];
                    if(mp[i][j+2]&& !(k&mov(j))&& (k&mov(j+1))) f[i][j+1][k]+=f[i][j][k];
                    if((k&mov(j))&& (k&mov(j+1))) f[i][j+1][(k^mov(j))^mov(j+1)]+=f[i][j][k];
                }
                else f[i][j+1][k]+=f[i][j][k];
            }
        }
        for(int k=0; k<mov(m+1); k++)f[i+1][0][(k<<1)&(mov(m+1)-1)]+=f[i][m][k];
    }
    return f[n][m][0];
}

void init()
{
    memset(f, 0, sizeof(f));
}

int main()
{
    int T;
    scanf("%d", &T);
    for(int i=1; i<=T; i++)
    {
        input();
        init();
        printf("Case %d: There are %lld ways to eat the trees.\n", i, work());
    }
    return 0;
}

Tony’s Tour(POJ1739)

​ 这道题给出一个 n*m 的方格，求一条从左下角到右下角的路径遍历所有非障碍方格。

​ 如果在图的下方补两行则可以将问题转化为 “用一个环覆盖所有方格”

​ 如果我们像普通的插头 Dp 一样开数组，转移状态，我们会 MLE。这是因为状态数太多… 怎么办？由于我们发现实际用到的状态数很少，所以我们不妨将所有状态 HASH 一下，将用到的状态保存在哈希表里。

​ 实际上我们会发现真正存在的状态并不多，因此像上一题一样枚举状态并不是很划算的处理方式。我们可以用栈或队列记录哪些 S 使得 f[i][j][S] 不为 0，这样可以更快地转移。实际上这样可以快大约 10 倍，但是由于我新学插头 DP 并没有想到这种优化，而且模仿之前题目的格式书写，导致运行较慢。而且由于书写格式与架构的问题，代码很长。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#define MX 12
#define SP 0
#define LB 1
#define RB 2
#define reg register
#define MOD 510511

using namespace std;

typedef unsigned long long ll;
typedef struct tstate
{
    int x;
    tstate(){}
    tstate(int a):x(a){}
    inline int get(int p){return ((x>>(p<<1))&3);}  //返回某一位的状态
    inline void set(int p,int s){x&=(~(3<<(p<<1)));x|=(s<<(p<<1));} //将某一位设为 s
    inline void operator ++ ()  //三进制自加
    {
        int p=0;
        ++this->x;
        while(get(p)==3)(this->x)+=(1<<(p<<1)),++p;
    }
    inline int other(int p) //找配对的括号
    {
        reg int cnt=0;
        if(get(p)==LB)
        {
            for(reg int i=p;i<=MX;i++)
            {
                if(get(i)==LB)cnt++;
                else if(get(i)==RB)cnt--;
                if(cnt==0)return i;
            }
        }
        else
        {
            for(reg int i=p;i>=0;i--)
            {
                if(get(i)==RB)cnt++;
                else if(get(i)==LB)cnt--;
                if(cnt==0)return i;
            }
        }
        return 0;
    }
}state;
typedef struct tnode    //哈希表
{
    int i,j;state x;
    tnode(){}
    tnode(int a,int b,int c):i(a),j(b),x(c){}
}node;
int n,m;
int mp[MX+2][MX+2];
int fst[MOD+1],nxt[1000001],hnum;
ll f[1000001];int hasnum[1000001];
int has(int i,int j,state s)
{
    int p=(i<<20)+(j<<26)+s.x;
    for(int x=fst[p%MOD];x;x=nxt[x])
        if(hasnum[x]==p)
            return x;
    return 0;
}
void add(int i,int j,state s,ll x)
{
    int p=(i<<20)+(j<<26)+s.x,pos=has(i,j,s);
    if(!pos)
    {
        nxt[++hnum]=fst[p%MOD];
        fst[p%MOD]=hnum;
        hasnum[hnum]=p;
        f[hnum]=x;
    }
    else f[pos]+=x;
}

void input()
{
    char ch;
    scanf("%d%d",&n,&m);
    for(reg int i=1;i<=n;i++)
        for(reg int j=1;j<=m;j++)
        {
            ch=getchar();
            while(ch!='.'&&ch!='#')ch=getchar();
            if(ch=='.')mp[i][j]=1;
            else mp[i][j]=0;
        }
    for(reg int i=0;i<=n+3;i++)mp[i][0]=mp[i][m+1]=0;
    for(reg int i=0;i<=m+1;i++)mp[0][i]=mp[n+3][i]=0;
    for(reg int i=2;i<m;i++)mp[n+1][i]=0;
    for(reg int i=1;i<=m;i++)mp[n+2][i]=1;
    mp[n+1][1]=mp[n+1][m]=1;
}

void work()
{
    state t;
    add(1,0,(state)(0),1);
    for(reg int i=1;i<=n+2;i++)
    {
        for(reg int j=0;j<m;j++)
        {
            for(state s(0);s.x<(1<<((m+1)<<1));++s)
            {
                if(!has(i,j,s))continue;
                if(mp[i][j+1])
                {
                    if(s.get(j)&&!s.get(j+1)&&mp[i][j+2])
                    {
                        t=s;t.set(j+1,s.get(j)),t.set(j,SP);
                        add(i,j+1,t,f[has(i,j,s)]);
                    }
                    if(s.get(j)&&!s.get(j+1)&&mp[i+1][j+1])
                    {
                        t=s;
                        add(i,j+1,t,f[has(i,j,s)]);
                    }
                    if(!s.get(j)&&s.get(j+1)&&mp[i+1][j+1])
                    {
                        t=s;t.set(j+1,SP),t.set(j,s.get(j+1));
                        add(i,j+1,t,f[has(i,j,s)]);
                    }
                    if(!s.get(j)&&s.get(j+1)&&mp[i][j+2])
                    {
                        t=s;
                        add(i,j+1,t,f[has(i,j,s)]);
                    }
                    if(s.get(j)==RB&&s.get(j+1)==RB)
                    {
                        t=s;t.set(t.other(j),RB),t.set(j,SP),t.set(j+1,SP);
                        add(i,j+1,t,f[has(i,j,s)]);
                    }
                    if(s.get(j)==LB&&s.get(j+1)==LB)
                    {
                        t=s;t.set(t.other(j+1),LB),t.set(j,SP),t.set(j+1,SP);
                        add(i,j+1,t,f[has(i,j,s)]);
                    }
                    if(s.get(j)==RB&&s.get(j+1)==LB)
                    {
                        t=s;t.set(j,SP),t.set(j+1,SP);
                        add(i,j+1,t,f[has(i,j,s)]);
                    }
                    if(!s.get(j)&&!s.get(j+1)&&mp[i+1][j+1]&&mp[i][j+2])
                    {
                        t=s;t.set(j,LB),t.set(j+1,RB);
                        add(i,j+1,t,f[has(i,j,s)]);
                    }
                    if(s.get(j)==LB&&s.get(j+1)==RB&&i==n+2&&j==m-1)
                    {
                        t=s;t.set(j,SP),t.set(j+1,SP);
                        add(i,j+1,t,f[has(i,j,s)]);
                    }
                }
                else
                {
                    t=s;t.set(j,0),t.set(j+1,0);
                    add(i,j+1,t,f[has(i,j,s)]);
                }
            }
        }
        for(state s(0);s.x<(1<<((m+1)<<1));++s)
        {ti
            if(!has(i,m,s))continue;
            t=s;t.x<<=2;t.set(m+1,0);
            add(i+1,0,t,f[has(i,m,s)]);
        }
    }
    printf("%lld\n",f[has(n+2,m,(state)(0))]);
}

int main()
{
    while(1)
    {
        hnum=0;
        input();
        if(n==0&&m==0)break;
        work();
        memset(fst,0,sizeof(fst));
    }
    return 0;
}

地图 (GDKOI2016DAY1)

​ 题意是：给出一个 n*m 的地图 ($n,m\leq 7​$). 地图上存在已知的”S”，”X”，”E”，”#”，”.”，还有未知的点。一个合法的地图满足”S”，”X”，”E” 有且仅有一个且两两通过”.” 或自身连通。如果未知的点可以改成任何一种符号，求所有可能的合法地图的总数。

​ 本题我偷懒使用了 pbds 的哈希表，由于修改了架构，采用栈记录状态，这个程序跑得比较快，而且代码相比于上一题更为精简。

​ 由于本题限制较多，代码可能不是很优美。

#pragma GCC optimize(2)
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#define MOD 1000000007LL
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned int ui;

int n,m,now;
char mp[8][8],lst[5]={'S','X','E','.','#'};
cc_hash_table<int,ll>f[2];
cc_hash_table<int,bool>inq;
int hav[3],q[130000],avl[130000],num,top;
inline int cprs(int *a)                     //compress: 将数组表示的状态转化为一个数字
{
    int h=0;
    for(int i=1;i<=m+3;i++)h=h*8+a[i];
    return h;
}
inline void dprs(int *a,int h)              //de-compress: 将一个数字解压为一个数组状态
{
    a[0]=0;
    for(int i=m+3;i>=1;i--)a[i]=h%8,h/=8;
}
inline void normal(int *a)                  //将一个状态最小表示
{
    int vis[11],c=0;memset(vis,0,sizeof(vis));
    for(int i=1;i<=m+3;i++)if(!vis[a[i]]&&a[i])vis[a[i]]=++c;
    for(int i=1;i<=m+3;i++)a[i]=vis[a[i]];
}
inline void obstacle(int x,int y,int st)    //放置一个障碍
{
    int nst,arr[11];
    dprs(arr,st);
    arr[y]=0;
    normal(arr);
    nst=cprs(arr);
    f[now^1][nst]=(f[now^1][nst]+f[now][st])%MOD;
    if(!inq[nst])q[++top]=nst,inq[nst]=1;
}
inline void space(int x,int y,int st)       //放置一个非障碍格
{
    int nst,arr[11];
    dprs(arr,st);
    if( (mp[x][y]=='S'&&arr[m+1])||
        (mp[x][y]=='X'&&arr[m+2])||
        (mp[x][y]=='E'&&arr[m+3]))return;   //如果已经出现过 SEX, 则跳过
    if(!arr[y-1]&&!arr[y])arr[y]=10;        //新建一个连通块
    else if(!arr[y-1]&&arr[y]);
    else if(arr[y-1]&&!arr[y])arr[y]=arr[y-1];
    else                                    //合并两个连通块
    {
        int s=arr[y-1],t=arr[y];
        for(int i=1;i<=m+3;i++)if(arr[i]==t)arr[i]=s;
    }
    normal(arr);
    if(mp[x][y]=='S')arr[m+1]=arr[y];
    else if(mp[x][y]=='X')arr[m+2]=arr[y];
    else if(mp[x][y]=='E')arr[m+3]=arr[y];
    nst=cprs(arr);
    f[now^1][nst]=(f[now^1][nst]+f[now][st])%MOD;
    if(!inq[nst])q[++top]=nst,inq[nst]=1;
}
void work()
{
    f[now=0][0]=1;
    q[++top]=0,inq[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(register int k=1;k<=top;k++)avl[k]=q[k],inq[q[k]]=0;//从栈中提取出状态
            num=top;top=0;
            for(register int k=1;k<=num;k++)
            {
                if(mp[i][j]=='#')obstacle(i,j,avl[k]);
                else if(mp[i][j]=='?')
                {
                    char old=mp[i][j];
                    for(int l=0;l<=4;l++)
                    {
                        if(l<=2&&hav[l])continue;
                        mp[i][j]=lst[l];
                        if(mp[i][j]=='#')obstacle(i,j,avl[k]);
                        else space(i,j,avl[k]);
                    }
                    mp[i][j]=old;
                }
                else space(i,j,avl[k]);
                f[now][avl[k]]=0;
            }
            now^=1;
        }
    }
}
void print()
{
    ll ans=0;int arr[11];
    for(register int i=1;i<=top;i++)
    {
        dprs(arr,q[i]);
        if(!arr[m+1]||!arr[m+2]||!arr[m+3])continue;
        else if(arr[m+1]==arr[m+2]&&arr[m+2]==arr[m+3])ans=(ans+f[now][q[i]])%MOD;
    }
    printf("%lld\n",ans);
}
void input()
{
    char ch;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ch=getchar();
            while(ch==' '||ch=='\n'||ch=='\r')ch=getchar();
            mp[i][j]=ch;
            for(int k=0;k<=2;k++)if(mp[i][j]==lst[k])hav[k]=1;
        }
    }
}
int main()
{
    input();
    work();
    print();
    return 0;
}
分类： 文章

3 条评论

nikkukun · 2019年8月24日 7:18 下午

写的好棒哇，学习到了

回复

Rayment · 2018年8月22日 8:13 下午

入门第二题就是 poj1739，还有人性吗……

回复

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注