状态压缩--习题分享

蒙德里安

f[i][j]：现在要摆第i列，上1列伸出方格的状态为j

所谓的状态压缩DP，就是用二进制数保存状态，通过位运算来求得结果

难点一：

题目问题转化

本题等价于找到所有横放 1 X 2 小方格的方案数，因为所有横放确定了，那么竖放方案是唯一的

状态转移方程

用f[i][j]记录第i列第j个状态。j状态位等于1表示上一列有横放格子，本列有格子捅出来。转移方程很简单，本列的每一个状态都由上列所有“合法”状态转移过来f[i][j] += f[i - 1][k]

状态转移条件

• j 列和j的前一列k列同一行不同时捅出来，也就是判断是否重叠 (j&k)==0
• j 列和j的前一列k列相或后不能存在连续奇数个空行 j|k

难点二：

预处理状态

如果有n行，意味着每一列存在2^n种可能，0~2^n每一个数字代表着一种可能，通过位运算判断这一个数字中是否出现连续的0，将不满足条件的列打上标记

package 动态规划.状态压缩.蒙德里安;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N=12;
    static int M=1<<N;
    static long[][] f=new long[N][M];
    static boolean[] st=new boolean[M];
    static int n,m;

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (true){
            n=sc.nextInt();
            m=sc.nextInt();
            if(n==m&&n==0)break;
            //预处理st数组,筛选出哪一列的状态可以摆
            for (int i=0;i<1<<n;i++){
                st[i]=true;
                int cnt=0;
                for(int j=0;j<n;j++){
                    //通过位运算，i状态下j行是否放方格
                    //0就是不放，1就是放
                    //i>>j是位运算，表示获得i的每一位
                    if((i>>j&1)==1){
                        //判断是否存在奇数个0
                        if((cnt&1)==1){
                            st[i]=false;
                            break;
                        }
                    }else cnt++;
                }
                //处理高位0的个数，如4：0100，当走到1这一位时
                //就停止了，但是还有一个高位0需要处理
                if((cnt&1)==1)st[i]=false;
            }

            for(int i=0;i<N;i++)
                Arrays.fill(f[i],0);
            //棋盘是从第0列开始，没有-1列，所以第0列第0行，不会有延伸出来的小方块
//        没有横着摆放的小方块，所有小方块都是竖着摆放的，这种状态记录为一种方案
            f[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((j&k)==0&&st[j|k])
                            f[i][j]+=f[i-1][k];

            System.out.println(f[m][0]);
        }
    }
}

最短Hamilton路径

本题同样是状态压缩，从第0号点走到第n-1号点，用二进制来表示要走的所以情况的路径,这里用i来代替

例如走0,1,2,4这三个点,则表示为:10111;走0,2,3这三个点:1101;走过就为1，没走就为0，要找的是走过所有点到达第n-1个点，所以得到集合：所有从0走到j,走过的所有点的情况是i的所有路径，属性是最小值

状态计算则是从倒数第二个点开始计算

package study;

import java.io.*;
import java.util.*;

public class Main {
    static int N=20;
    static int M=1<<N;
    static int[][] w=new int[N][N];
    static int[][] f=new int[M][N];
    public static void main(String[] args)throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] s;
        int n=Integer.parseInt(br.readLine());
        /**
         * 读入边权数据
         */
        for(int i=0;i<n;i++){
            s=br.readLine().split(" ");
            for(int j=0;j<n;j++)
                w[i][j] = Integer.parseInt(s[j]);
        }
        /**
         * 因为找最小，所以赋值成最大
         */
        for(int i=0;i<1<<n;i++)
            Arrays.fill(f[i],0x3f3f3f3f);
        /**
         * 因为第0号点走了
         */
        f[1][0]=0;
        for(int i=0;i<1<<n;i++){
            for(int j=0;j<n;j++){
                /**
                 * 遍历i的每一位，
                 * 因为i是走过所有点情况的所有路径，
                 * 所以，i中一定要包含j这个点
                 */
                if((i>>j&1)==1){
                    for(int k=0;k<n;k++){
                        /**
                         * 同上，i中也要包含k这个点
                         */
                        if((i>>k&1)==1){
                            f[i][j]=Math.min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
                        }
                    }
                }
            }
        }
        /**
         * (1<<n)-1结果为111111，表示走过所有点
         * n-1，表示终点是n-1的最短距离
         */
        System.out.println(f[(1<<n)-1][n-1]);
    }
}