这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的8个格子，求使它们无法互相攻击的方案总数。

输入格式
共一行，包含两个整数 n 和 k

输出格式
共一行，表示方案总数，若不能够放置则输出0

数据范围
1≤n≤10

0≤k≤n^2
输入样例：
3 2
输出样例：
16
难度：简单
时/空限制：1s / 64MB

来源：《信息学奥赛一本通》, SGU223, SCOI2005
算法标签
状态压缩DP

思考

这道题的思想极其类似蒙德里安的梦想，关于这道题我有不下于千字的讲解，大家可以去看看，包括很多细节和边界条件的阐述

传送门：我的蒙德里安的题解

我们发现这题也是棋盘类的状态压缩状态，第 i行的状态和前一行后一行都有关联，所以不妨我们就从上到下去枚举状态，这样考虑第i行的状态只需要考虑第i - 1行的状态

那么我们的动态规划就可以这么来看f[i][j][a] ---> 前i行放j个国王，状态为a的总方案数量

我们这里先给大家科普我们如何计算一个状态的国王数量，其实就是求二进制状态有几位1

    static int count(int state) {
        int res = 0;
        for (int i = 0; i < n; i++) {
            if ((state >> i & 1) == 1) {
                res++;
            }
        }
        return res;
    }

再来说明一下一个状态如何才算合法

    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;
    }

需要满足一行没有相邻的1才行，那么如何判断两个相邻的行怎么才能合法？
和我们蒙德里安部分的分析相同，当满足 (a & b) == 0 即两行没有交集算第一个合法条件，同时此时求a | b,代表两个状态求并集，这个理由在蒙德里安讲过，此时也需要满足并集状态也没有相邻的1

我们的状态转移根据闫式dp分析法，可以这么考虑，当前的状态只能是合法的前一行(i - 1)的状态为b，放了当前状态计算二进制有几个1代表国王数量，各种合法相邻的情况的求和才行，而国王数加上目前的第i行的count(a) 需要满足等于 k

为什么最后多了一维遍历，答案是f[n+1][k][0]?
答案本来按我们原定想法是从最后一行f[i][k][]循环找到底答案是最后一行放几个,状态为什么，可以利用遍历states，然后利用_count函数_计算它的国王数量,但是我们为什么多开一维的状态方程——》因为我们可以利用多计算一行的状态方程,此时n + 1行，一个国王也不放，并且状态为0就是前n行合法的全部方案数

JAVA代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.BlockingDeque;

public class Main {
    static int N = 12, M = 1 << 10, K = 110;
    static int n, k;
    static long[][][] f = new long[N][K][M];
    static List<Integer> states = new ArrayList<Integer>();
    static int[] cnt = new int[M];
    static ArrayList<Integer>[] head = new ArrayList[M];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    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;
        for (int i = 0; i < n; i++) {
            if ((state >> i & 1) == 1) {
                res++;
            }
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        k = Integer.parseInt(s[1]);
        //所有合法状态存储
        for (int i = 0; i < 1 << n; i++) {
            if (check(i)) {
                states.add(i);
                cnt[i] = count(i);
            }
        }
        //找寻它可以转换到的状态,其实也可以说是能转移到它的状态
        for (int i = 0; i < states.size(); i++) {
            for (int j = 0; j < states.size(); j++) {
                int a = states.get(i);
                int b = states.get(j);
                if ((a & b) == 0 && check(a | b)) {
                    //ArrayList数组默认初始化每个元素是null
                    if (head[i] == null)
                        head[i] = new ArrayList<Integer>();
                    head[i].add(j);
                }
            }
        }
        //初始化初值
        f[0][0][0] = 1;
        //动态规划
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 0; j <= k; j++) {
                for (int a = 0; a < states.size(); a++) {
                    for (int b : head[a]) {
                        int c = cnt[states.get(a)];
                        if (j >= c) {
                            f[i][j][a] += f[i - 1][j - c][b];
                        }
                    }
                }
            }
        }
        //答案本来按我们原定想法是从最后一行f[i][][]循环找到底答案是最后一行放几个
        //状态为什么，可以利用遍历states，然后利用count函数计算它的国王数量
        //但是我们为什么多开一维的状态方程——》因为我们可以利用多计算一行的状态方程
        //此时 n + 1 行，一个国王也不放，并且状态为0就是前n行合法的全部方案数
        System.out.println(f[n+1][k][0]);
    }
}