当前位置：首页 > article >正文

状压DP

article 2024/11/15 12:19:21

状压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 \leq N, M \leq 11$

输入样例

输出样例

分析

状压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数组，届时判断 $s t [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 \leq n \leq 20$
$0≤a[i,j]≤10^7$

输入样例

输出样例

分析

定义 $f [i, j]$ 为以j为终点，通过路径状态压缩后为i的所有方案，最终答案是 $f [1 << n - 1] [n - 1]$ ，用k表示前一个状态，枚举所有的j，i，k，判断i内是否包含终点j和前一个点k，若包含，则 $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;
}