5、状态压缩DP &蒙德里安的梦想 &最短Hamilton路径

AcWing 291. 蒙德里安的梦想

AcWing 91. 最短Hamilton路径

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int N = 12,M=1<<N;
    boolean st[] = new boolean[M];
    long f[][] = new long[N][M];
    void init() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();
        while (N != 0 && M != 0) {
            for (int i = 0; i < (1 << N); i++) {
                st[i] = true;
                int cnt = 0;
                for (int j = 0; j < N; j++) {
                    if (((i >> j) & 1) != 0) {
                        if ((cnt & 1) != 0) {
                            st[i] = false;
                            break;
                        }
                    } else cnt++;
                }
                if ((cnt & 1) != 0) st[i] = false;
            }
            for (int i = 0; i < f.length; i++) {
                Arrays.fill(f[i], 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]);
            N = sc.nextInt();
            M = sc.nextInt();
        }
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = 20,M = 1 << N;
        int[][] f = new int[M][N];//当前的状态是i，然后走到了点j上面
        int[][] w = new int[N][N];
        int n = scan.nextInt();
        for(int i = 0 ; i < n ; i ++ )
            for(int j = 0 ; j < n ; j ++ )
                w[i][j] = scan.nextInt(); // 输入每一步的权重

        for(int i = 0 ; i < 1 << n ; i ++ )
            Arrays.fill(f[i],0x3f3f3f); //除了第一个点，其他点初始化成正无穷
        f[1][0] = 0;

        //首先枚举一下所有的状态
        for(int state = 0 ; state < 1 << n ; state ++ ){
            //一共有多少步
            for(int j = 0 ; j < n ; j ++ ){
                // 表示能够走到j,才能进行下一步
                if((state >> j & 1) == 1){
                    //我们用倒数第二步来化整为零

                    for(int k = 0 ; k < n ; k ++ ){
                        //首先减掉最后一个点剩下的路径中要能够走到k才能够进行状态计算
                        if((state - (1 << j) >> k & 1) == 1){
                            //0 - k - j的途径 f[state - (1 << j)][k] + w[k][j]
                            f[state][j] = Math.min(f[state][j],f[state - (1 << j)][k] + w[k][j]);
                        }
                    }
                }
            }
        }
        //最后输出从定义出发，不难想到，f[state][j],state表示的是二进制的全0表示都走过，j表示从0走到n-1
        System.out.println(f[(1 << n) - 1][n - 1]);
    }
}