AcWing 1064. 小国王(预处理所有合法状态和合法转移)
原题链接
简单
作者:
半透明の微笑
,
2024-04-15 21:05:44
,
所有人可见
,
阅读 9
import java.io.*;
import java.util.*;
public class Main{
static int N = 12;
static int K = N * N;
static int M = 1 << N;
static int n, m;
static long[][][] f = new long[N][K][M];
static ArrayList<Integer> state = new ArrayList<>();
static ArrayList<Integer>[] head = new ArrayList[M];
static int[] cnt = new int[M];
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;
}
static int count(int state){
int res = 0;
while(state != 0){
if((state & 1) == 1) res ++;
state >>= 1;
}
return res;
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
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 ++) head[i] = new ArrayList<>();
for(int i = 0; i < state.size(); i ++){
int a = state.get(i);
for(int j = 0; j < state.size(); j ++){
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 k = 0; k < state.size(); k ++){
for(int d : head[k]){
int num = cnt[state.get(k)];
if(j >= num) f[i][j][k] += f[i - 1][j - num][d];
}
}
}
}
System.out.println(f[n + 1][m][0]);
}
}