轮廓线 dp 也是一种状压,适用于一维特别大而另一维特别小的情况。
我们来从一道经典例题入手:求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。
如果 $n,m \leq 11$ 那么当然可以轻松状压了,但是如果 $n = 10^5$ ,我们就要考虑使用轮廓线 dp 了。
设 $f_{i,S}$ 表示我们填到第 $i$ 行,我们在状压的状态中记录下图红线上的格子的状态。

(圆圈为现在要填的格子)
发现对于一个格子 我们只需要考虑这个格子上是放向上的骨牌,还是向左还是不放。如果上面是空格子那么必须要放向上的格子,否则向左和不放都可以。
考虑放了向上的格子后变成了什么:

发现只有填的那个位置变成了 $1$ 直接简单位运算操作一下就可以了。
其他状态可以尝试自己推一下,实在不懂了可以去看代码(

/*
 * Author: RainAir
 * Time: 2019-08-25 11:31:00
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = (1<<15) + 5;
int f2,now;
int n,m;

inline void Solve(){
    if(n < m) std::swap(n,m);
    now = 0;CLR(f,0);
    fnow = 1;
    FOR(i,0,n-1){
        FOR(j,0,m-1){
            CLR(f[now^1],0);
            FOR(S,0,(1<<m)-1){
                if(!(S&(1<<j))){
                    fnow^1 += fnow;
                }
                else{
                    fnow^1 += fnow;
                    if(j > 0 && !(S&(1<<j-1))){
                        fnow^1 += fnow;
                    }
                }
            }
            now ^= 1;
        }
    }
    printf("%lldn",fnow);
}

signed main(){
    while(~scanf("%lld%lld",&n,&m) && (n+m)) Solve();
    return 0;
}

<h2>一个进阶小题</h2>

我们考虑如果可以使用 $1\times 1$ 和 $1\times 2$ 的块,并且限制 $1\times 1$ 的使用次数,限制某些块不能填,那么怎么做?(HDU 4804
也可以设 $f_{i,j,S}$ 表示第 $i$ 行用了 $j$ 个 $1\times 1$,轮廓线的状态。
只需要按照上面和定义转移就可以了,注意判断一下如果这个格子被限制不能填的话直接从上一个状态转移就可以了。

/*
 * Author: RainAir
 * Time: 2019-08-25 14:57:19
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100+5;
const int MAXM = 11;
const int ha = 1e9 + 7;
int n,m,C,D,now=0;
int f2[3005];
char mpMAXN;

inline void Solve(){
    CLR(f,0);now = 0;
    FOR(i,0,n-1){
        scanf("%s",mp[i]);
    }
    fnow[(1<<m)-1] = 1;
    FOR(i,0,n-1){
        FOR(j,0,m-1){
            CLR(f[now^1],0);
            if(mpi != '0'){
                FOR(k,0,D){
                    FOR(S,0,(1<<m)-1){
                        if(k && (S&(1<<j)))
                            (fnow^1[S] += fnow[S]) %= ha;
                        (fnow^1[S^(1<<j)] += fnow[S]) %= ha;
                        if(j && !(S&(1<<j-1)) && (S&(1<<j)))
                            (fnow^1[S|(1<<j)|(1<<j-1)] += fnow[S]) %= ha;
                    }
                }
            }
            else{
                FOR(k,0,D){
                    FOR(S,0,(1<<m)-1)
                        if((1<<j) & S)
                            (fnow^1[S] += fnow[S]) %= ha;
                }
            }
            now ^= 1;
        }
    }
    int ans = 0;
    FOR(i,C,D) (ans += fnow[(1<<m)-1]) %= ha;
    printf("%dn",ans);
}

int main(){
    while(~scanf("%d%d%d%d",&n,&m,&C,&D)) Solve();
    return 0;
}
Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏