第一章动态规划（九）

状态压缩DP

例题：1064.骑士

————————————————————————————————————————————————————

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int N = 55;
	static int M = 1 << 10;
	static int K = 110;
	static int n;
	static int m;
	static int[] cnt = new int[M];
	static ArrayList<Integer>[] head = new ArrayList[M]; 
	static ArrayList<Integer> state = new ArrayList<>();
	static long[][][] f = new long[N][K][M];

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		sc.close();
		
		for (int i = 0; i < head.length; i++) {
			head[i] = new ArrayList<>();
		}
		for(int i = 0;i < 1 << n;i++) {
			if(check(i)) {
				state.add(i);
				cnt[i] = count(i);
			}
		}
		for(int i = 0;i < state.size();i++) {
			for (int j = 0; j < state.size(); j++) {
				int a = state.get(i);
				int b = state.get(j);
				if((a & b) == 0 && check(a | b)) {
					head[i].add(j);
				}
			}
		}
		f[0][0][0] = 1;
		for (int i = 1; i <= n + 1; i++) {
			for (int j = 0; j <= m; j++) {
				for (int a = 0; a < state.size(); a++) {
					for(int b : head[a]) {
						int c = cnt[state.get(a)];
						if(j >= c) {
							f[i][j][a] += f[i - 1][j - c][b];
						}
					}
				}
			}
		}
		System.out.println(f[n + 1][m][0]);
	}

	private static int count(int state) {//返回1的个数
		int res = 0;
		for (int i = 0; i < n; i++) {
			res += (state >> i) & 1;
		}
		return res;
	}

	private static boolean check(int state) {//状态是否合法
		for(int i = 0;i < n;i++) {
			if(((state >> i) & 1) == 1 && ((state >> i + 1) & 1) == 1)
				return false;
		}
		return true;
	}
}