轮廓线DP

Gaochenxi103_QAQ · 2026-01-12 16:00:01 · 算法·理论

算法概述

轮廓线 DP，是属于状压 DP 的一个衍生算法。它相较于普通的状压在算法复杂度上会有所优化。

它较难的衍生是插头 DP，但本文不做展开。~~【因为作者不会】~~

当我们发现问题有如下特征是就大概率可以用轮廓线 DP。

可以抽象成网格问题；
每个“格点”会受周围“格点”的约束且范围一般很小；【比如相邻】
某一维的范围很小，状压可以接受。
是个 DP 可以求解的问题。【如计数，最值等】

算法内容

例1 Corn Fields G

题目简述：给出一个 12\times 12 的网格，每个格点根据输入得知是否可选。统计合法方案数，对于一个方案而言，不存在相邻的选择格点。

显然可以用朴素的状压 dp[i][msk] 表示第 i 行选择情况为 msk 的方案数。

::::info[朴素状压代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e8;
const int N=1e5+10;
int n,m,dp[15][N];
bool vis[15][15];
bool check(int x,int k)
{
    vector<int>a(1);
    int ld=x;
    while(x)
    {
        a.push_back(x%2);
        x/=2;
    }
    for(int i=1;i<a.size();i++)
    {
        if(!vis[k][i] && a[i])return false;
        if(i>1 && a[i-1]==a[i] && a[i])return false;
    }
    return true;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>vis[i][j];
        }
    }

    for(int i=0;i<(1<<m);i++)
    {
        if(!check(i,1))continue;
//      cout<<i<<"\n";
        dp[1][i]=1;
    }

    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<(1<<m);j++)
        {
            if(!check(j,i))continue;
            for(int k=0;k<(1<<m);k++)
            {
                if(!check(k,i-1))continue;
                int x=j,y=k;
                bool flag=false;
                while(x&&y)
                {
                    if(x%2 && y%2)
                    {
                        flag=true;
                        break;
                    }
                    x/=2,y/=2;
                }
                if(flag)continue;
                dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
            }
        }
    }

    int ans=0;
    for(int i=0;i<(1<<m);i++)ans=(ans+dp[n][i])%mod;
    cout<<ans;
    return 0;
}

::::

时间复杂度应该最坏是 O(n\times2^{n}\times(n+2^{n}))。【实际上完全达不到】直接看运行结果通过本题绰绰有余，但我们要引入一个轮廓线的做法在时间复杂度上更优。

最基础的状压是一层一层转移的，而我们可以一格一格的转移。对于一个点 (i,j) 它是否可以转移只与它上面一个和左边一个有关。那么我们将 (i-1,j) 到 (i,j-1) 这 n 个的选择情况压起来是不是就可以判断这个 (i,j) 可不可选？

如图，橙色是 (i,j)，对于其的轮廓线就是蓝色的这一条。

我们只需要知道它蓝色那条轮廓线的状态就可以判断当前状态和之后状态的转移了。

我们定义。

我们认为 msk 的二进制从高到低依次表示 (i-1,j) 到 (i-1,m) 再从 (i,1) 到 (i,j-1)。用我为人人的思路转移，因为这样可以 O(1) 确定当前状态可以转移到的状态的轮廓线。

比如当前我们选择种草，你们对于我们下一个格子他的轮廓线就是 msk'=(msk\times 2+1)\bmod 2^m。即将轮廓线向左移一位并除去最高位的溢出，再加上 1 表示下一个格子左边（当前格子）种了草。【最低位轮廓线为 1】

而这么判断是否可以种草。首先输入确定这里可以种草，其次这个格子的上方和左边不能种草。【不用关心右下，因为右下种草的时候会关心当前格子】对于这里的轮廓线，判断最高位和最低位是不是有为 1 的即可。注意当 j=1 的时候不需要判断最低位。

如果不种草则不加一，当 j=m 时，将轮廓线转移给 (i+1,1) 即可。最后答案就是 \sum_{msk=0}^{2^m-1}dp[n+1][1][msk]。【最后一行下一行第一个】

最后初始化就将dp[1][1][0]=1即可。因为第 0 行不会对第一行做任何的限制，所以只有dp[1][1][0]=1。

::::success[轮廓线做法代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=100000000;
int n,m;
bool vis[15][15];
int dp[15][15][1<<12];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>vis[i][j];
        }
    }

    dp[1][1][0]=1;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<(1<<m);k++)
            {
                dp[i][j][k]%=mod;
                if(vis[i][j] && (j==1 || !(k%2)) && !(k>>(m-1)))//(i,j)种草 
                {
                    int now=(k*2+1)%(1<<m);
                    if(j==m)dp[i+1][1][now]+=dp[i][j][k];
                    else dp[i][j+1][now]+=dp[i][j][k];
                }
                int nwe=(k<<1)%(1<<m);
                if(j==m)dp[i+1][1][nwe]+=dp[i][j][k];
                else dp[i][j+1][nwe]+=dp[i][j][k];

            }
        }
    }
    int ans=0;
    for(int k=0;k<(1<<m);k++)
    {
        // cout<<k<<" "<<dp[n+1][1][k]<<"\n";
        ans=(ans+dp[n+1][1][k])%mod;    
    }
    cout<<ans;
    return 0;
}

::::

这样的时间复杂度为 O(n^2\times 2^n)。虽在本题中体现不大，但综合来说是优于一般做法的。

::::info[测评结果对比]

直接状压

轮廓线做法

::::

例2 Mondriaan's Dream

题目简述：1\times 2 的骨牌填 n\times m(n,m\le 12) 的网格，在填满的情况下问有多少种不同的填法。

非常经典的骨牌题目，首先明确每个格子有 4 种状态。分别是和上面的形成一个骨牌和下面的形成一个骨牌和左边的形成一个骨牌和右边的形成一个骨牌。我们显然可以发现行内横着放的骨牌可以直接预处理处理合法情况，然后变成三维问题。然后就可以写出一个很极限通过本题的直接状压做法。

【看看做法就行，本文重点不在这】 ::::warning[三进制状压做法] 我们发现当前需要上面依赖的格子上面只能是依赖下面的，在每次转移一层前先预处理一下可以转移到这个状态的方案数hd()函数。

【最后跑了829ms】

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,m,dp[15][N];
//位置为0表示为横着的纸的一部分，为1表示和下一行的形成一部分，为2表示与上面的形成一部分 
struct S{
    int val[25]={0};
};

S work(int itm)
{
    S res;
    for(int i=1;i<=m;i++)
    {
        res.val[i]=itm%3;
        itm/=3;
    }
    return res;
}
void init()
{
    for(int i=0;i<pow(3,m);i++)
    {
        S now=work(i);
        bool flag=false;
        int l=-1;
        for(int j=1;j<=m;j++)
        {
            if(now.val[j]==0)
            {
                if(l==-1)l=j;
            }
            else
            {
                if(l!=-1)
                {
                    if((j-l)%2!=0)
                    {
                        flag=true;
                        break;
                    }
                }
                l=-1; 
            }
            if(now.val[j]==2)
            {
                flag=true;
                break;
            }
        }
        if(flag)continue;
        if(l!=-1 && (m-l+1)%2)continue;
        dp[1][i]=1;
    }
}
int f[3000]; 
int hd(S itm)//可以和itm匹配的方案数 
{
    int cnt=0;
    for(int k=1;k<=m;k++)
    {
        cnt*=2;
        if(itm.val[k]==2)
        {
            cnt+=1;
        }
    }
    return f[cnt];
}
void pre(int i)
{   
    memset(f,0,sizeof f);
    for(int j=0;j<pow(3,m);j++)
    {
        int cnt=0;
        S now=work(j);
        bool flag=false;
        int l=-1;
        for(int k=1;k<=m;k++)
        {
            if(now.val[k]==0)
            {
                if(l==-1)l=k;
            }
            else
            {
                if(l!=-1)
                {
                    if((k-l)%2!=0)
                    {
                        flag=true;
                        break;
                    }
                }
                l=-1; 
            }
            cnt*=2;
            if(now.val[k]==1)
            {
                cnt+=1;
            }
        }
        if(flag)continue;
        if(l!=-1 && (m-l+1)%2)continue;
        f[cnt]+=dp[i][j];
    }
}
void solve()
{
    if((n*m)%2!=0)
    {
        cout<<"0\n";
        return ;
    }
    init();
    int ans=0;
    for(int i=2;i<=n;i++)
    {
        pre(i-1);
        for(int j=0;j<pow(3,m);j++)
        {
            S now=work(j);
            bool flag=false;
            int l=-1;
            for(int k=1;k<=m;k++)
            {
                if(now.val[k]==0)
                {
                    if(l==-1)l=k;
                }
                else
                {
                    if(l!=-1)
                    {
                        if((k-l)%2!=0)
                        {
                            flag=true;
                            break;
                        }
                    }
                    l=-1; 
                }
            }
            if(flag)continue;
            if(l!=-1 && (m-l+1)%2)continue;
            dp[i][j]=hd(now);

        }
    }
    for(int i=0;i<pow(3,m);i++)
    {
        S now=work(i);
        bool flag=false;
        int l=-1;
        for(int k=1;k<=m;k++)
        {
            if(now.val[k]==1)
            {
                flag=true;
                break;
            }
            if(now.val[k]==0)
            {
                if(l==-1)l=k;
            }
            else
            {
                if(l!=-1)
                {
                    if((k-l)%2!=0)
                    {
                        flag=true;
                        break;
                    }
                }
                l=-1; 
            }
        }
        if(flag)continue;
        if(l!=-1 && (m-l+1)%2)continue;
        ans+=dp[n][i];
    }
    cout<<ans<<"\n";
    return ;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(1)
    {
        cin>>n>>m;
        if(n==0 && m==0)return 0;
        solve();
    }   
    return 0;
}

::::

对每个点的状态进行再一步的减少，0 表示不依赖下一行形成骨牌，1 表示依赖下一行形成骨牌。【当然推到这一步依然还是可以使用基本状压写】

回顾轮廓线的思路，这个位置的上方状态如果是 1，那么毫无疑问这里的状态是 0。可是行内状态为 0 即可能是和上面的形成一个骨牌，也可能是行内形成一个骨牌。依然是考虑我为人人的解决方法。

一个格子只考虑它和它右边的格子形成骨牌，将这个状态转移给它右边的右边格子即可。因为这样骨牌格子转移的时候就不会包含和右边人一起形成骨牌的方案数，自然就不会受影响。

所以，当格子上放为 1 时，这里这可能是 0 的状态，并将方案数转移给之后一个。

int now=(k<<1)%(1<<m);
if(j==m)dp[i+1][1][now]+=dp[i][j][k];
else dp[i][j+1][now]+=dp[i][j][k];

如果上面是 0 的状态，那么即可能这个格子状态为 1，方案数转移给右边的，也可能是和左边的形成骨牌。【但要判断左边是否还有格子，和左边格子上方是否不为 1】

int now=(k<<1)%(1<<m);
if(j!=m && !(now>>(m-1)))
{
    if(j==m-1) dp[i+1][1][(now<<1)%(1<<m)]+=dp[i][j][k];//横着摆一个
    else dp[i][j+2][(now<<1)%(1<<m)]+=dp[i][j][k];
}
if(j!=m)dp[i][j+1][now+1]+=dp[i][j][k];//这个位置和下面的配对 
else dp[i+1][1][now+1]+=dp[i][j][k];

最后答案就就是是dp[n+1][1][0]。因为最后一行不可能在和下一行的形成骨牌了。

初始化也是同理，因为第 1 行不会受到上层的约束，所以只有dp[1][1][0]=1。

最后在处理一下边界即可。

::::success[轮廓线做法代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[15][15][1<<13];
void solve(int n,int m)
{
    if(n*m%2)
    {
        cout<<"0\n";
        return ;
    }
    memset(dp,0,sizeof dp);
    dp[1][1][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<(1<<m);k++)
            {
                int now=(k<<1)%(1<<m);
                if(k>>(m-1))//头顶上的是1 
                {
                    //只能选0和上面配对 
                    if(j==m)dp[i+1][1][now]+=dp[i][j][k];
                    else dp[i][j+1][now]+=dp[i][j][k];
                }
                else
                {
                    if(j!=m && !(now>>(m-1)))
                    {
                        if(j==m-1) dp[i+1][1][(now<<1)%(1<<m)]+=dp[i][j][k];//横着摆一个
                        else dp[i][j+2][(now<<1)%(1<<m)]+=dp[i][j][k];
                    }
                    if(j!=m)dp[i][j+1][now+1]+=dp[i][j][k];//这个位置和下面的配对 
                    else dp[i+1][1][now+1]+=dp[i][j][k];
                }
            }
        }
    }
    cout<<dp[n+1][1][0]<<"\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(1)
    {
        int x,y;
        cin>>x>>y;
        if(x*y)solve(max(x,y),min(x,y));
        else break;
    }
    return 0;
}

:::: 而这道题目就可以体现出轮廓线时间上的优越性。 ::::info[测评结果对比]

轮廓线DP

算法概述

算法内容

例1 Corn Fields G

直接状压

轮廓线做法

例2 Mondriaan's Dream

普通做法

轮廓线做法

拓展题目

互不侵犯

炮兵阵地