状压DP

状压DP

对于数据范围n<=20的可以考虑状压DP

1.蒙德里安的梦想

题目描述

求把 $N\times M$ 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。

例如当$ N=2，M=4$ 时，共有 5 种方案。当 $N=2，M=3$ 时，共有 3 种方案。

如下图所示：

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 N 和 M。

当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

$1\le N,M\le 11$

输入样例

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例

1
0
1
2
3
5
144
51205

分析

状压DP模板题，本题若横着放的长方形确定，其他就只能竖着放，所以我们只需要考虑横着放的所有状态，定义f[i,j]为第i列伸出到第i+1列的状态为j的方案数，对于状压DP，每次假定前一个状态为k，则k为第i-1列伸到第i列的状态，枚举所有的j和k，判断是否符合条件即可

这里的条件是

• j和k的每一位不能同时为1，否则会出现长度为3的长方形：$j\&k==0$

• 第i列不能出现连续的奇数空，这里我们会出现一个问题，如何求第i列的状态，很容易想道第i列的状态是由第i-1伸到第i列和第i列伸到第i+1列共同引起的，所以第i列状态为$j|k$，对于每一列的状态，我们可以预处理一个st数组，届时判断$st[j|k]$是否为真即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=12,M=(1<<11)+10;
int dp[N][M];
bool st[M];
void init(int n)
{
    
    for(int i=0;i<1<<n;i++)
    {
        st[i]=true;
        int cnt=0;
        for(int j=0;j<n;j++)
        {
            int k=i>>j&1;
            if(k)
            {
                if(cnt&1) st[i]=false;
                cnt=0;
            }
            else cnt++;
        }
        if(cnt&1) st[i]=false;
    }
}
signed main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        init(n);
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<1<<n;j++)
            {
                for(int k=0;k<1<<n;k++)
                {
                    if((k&j)==0&&st[k|j]==true)
                    {
                        dp[i][j]+=dp[i-1][k];
                    }
                }
            }
        }
        cout<<dp[m][0]<<endl;
    }
    return 0;
}

2.最短哈密顿距离

题目描述

给定一张 n 个点的带权无向图，点从 $0\sim n-1$ 标号，求起点 0 到终点 $n-1$的最短 Hamilton 路径。

Hamilton 路径的定义是从 $0$ 到 n−1不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 $n$。

接下来 $n $行每行 $n$ 个整数，其中第 $i$ 行第$ j $个整数表示点$ i$ 到 $j $的距离（记为$ a[i,j]$）。

对于任意的 $x,y,z$，数据保证 $a[x,x]=0，a[x,y]=a[y,x]$ 并且$ a[x,y]+a[y,z]≥a[x,z]$。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

$1\le n\le 20$
$0\le a[i,j]\le 10^7$

输入样例

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例

18

分析

定义$f[i,j]$为以j为终点，通过路径状态压缩后为i的所有方案，最终答案是$f[1<<n-1][n-1]$，用k表示前一个状态，枚举所有的j，i，k，判断i内是否包含终点j和前一个点k，若包含，则 f [ i , j ] = M i n ( f [ i , j ] , f [ i − { j } ] [ k ] + a [ k , j ] ) f[i,j]=Min(f[i,j],f[i-\{j\}][k]+a[k,j]) f[i,j]=Min(f[i,j],f[i−{j}][k]+a[k,j])

代码

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=20,M=(1<<20)+10,inf=LLONG_MAX/2;

int f[M][N];
int a[N][N];
signed main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    
    int res=inf;
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    int cnt=0;
    for(int j=1;j<n;j++)
    {
        for(int i=0;i<1<<n;i++)
        {
            if(i&1==0) continue;
            if(i>>j&1)
            {
                for(int k=0;k<n;k++)
                {
                    if(i>>k&1)
                    {
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+a[k][j]);
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1]<<endl;
        
    return 0;
}