AcWing 1064 小国王

题目传送门

一、题目解析

国王可以向附近的八个方向进行攻击，所以穷举一下十六种可能，与测试用例对上了。

二、理解与感悟

每一行格子怎么摆，只和上一行有关系，和上上一行是没有关系的，这就是DP（递推) 的性质基础。

状态表示
\(f[i,j,s]\) 表示前\(i\)行已经做完了，当前已经放了\(j\)个国王，并且状态是\(s\)的所有方案的集合。\(s\)是一个二进制数，举个例子：
\(n=3\) \(101-->5\) \(010-->2\) ，所以\(s\)的范围就是\(0\)~\(2^n-1\)

属性
count

状态计算
集合划分的过程。f[i,j,？]=f[i-1,j-1,?]+f[i-1,j,?] 其中？都 代表了所有的合法摆放方式。
约束就是不能有两个相邻的，并且要满足i-1行和i行也是互相不能攻击到的。
a&b=0 a|b不能有相邻的。两个位运算就把上面的条件描述清楚了，真的是太经典了。
有同学说也可以使用（a>>1) & b ==0 && (a<<1) &b ==0，我也要试试，因为第一感觉就是这个思路。

这DP的思想，和数据库表的创建有相似的地方，就是看枚举出来的因素，是否能完事描述出这件事，如果不行，就需要加一维。

三、实现代码

#include 

using namespace std;
//棋盘式状态压缩DP

//方案数太多，如果最开始使用int，后面会溢出
typedef long long LL;

//棋盘的长宽上限，其实11就够用了，这里使用了12是因为最后统计时的一个小技巧。
const int N = 12;
const int M = 1 << 10;  //二进制枚举的状态数量上限，因为n最大是10,就是2^10个状态
const int K = 110;      //国王的个数上限
int n;                  //n*n的棋盘
int m;                  //国王的数量
vector st;         //所有合法的状态（预处理的结果）
int cnt[M];             //某个合法状态，使用了多少个国王

vector head[M];    //某个状态可以转移到的其它状态有哪些
LL f[N][K][M];
//递推的结果数组,第一维：已经完成前i行，第二维：已经使用了j个国王，
//第三维：现在的状态是x:001010111之类，存在的是二进制对应的十进制数

//检查一个状态是不是合法，指此状态是否有连续的1。
//有则表示存在连续国王，会打架，不合法
bool check(int state) {
    for (int i = 0; i < n; i++)
        if ((state >> i & 1) && (state >> (i + 1) & 1)) return false;
    return true;
}

//计算state中数字1的个数,用来统计，这样摆要使用几个国王
int count(int state) {
    int res = 0;
    //n次右移，求最后一位是不是1，然后累加，计算出此数有多少个数字1
    for (int i = 0; i < n; i++) res += state >> i & 1;
    return res;
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n >> m;

    //状态压缩DP的预处理
    for (int i = 0; i < 1 << n; i++)
        //如果状态合法
        if (check(i)) {
            st.push_back(i);       //记录合法状态
            cnt[i] = count(i);//此合法状态下使用了多少个国王
        }
    //预处理,建立两种状态之间的转移关系
    for (int i = 0; i < st.size(); i++)
        for (int j = 0; j < st.size(); j++) {
            int a = st[i], b = st[j];
            //a&b==0:同列不是同时为1，表示列上面国王不冲突
            //a|b :将两个二进制数叠加，每一位如果有一个1，最终此位就是1，都是0，才最终是0
            //check(a|b)： 经或处理后的数字，如果存在连续的1，就表示斜45度有国王，不合法，妙不可言
            if ((a & b) == 0 && check(a | b))
                head[i].push_back(j);//记录合法的状态转移关系
        }
    //开始DP
    f[0][0][0] = 1;
    //最开始的时候，我们f[0][0][0]=1
    /*什么意思呢，就是说，前0行对吧，我们前0行已经摆完了，其实也就是一行也没有摆的情况下，
    那么此时由于我们这个是在棋盘外面，所以肯定每个国王都不能摆对吧，所以我们就只有0
    这个状态时合法的，那么这个状态的方案数是1*/
    for (int i = 1; i <= n + 1; i++)            //第i行,注意这里特意多+了一个1
        for (int j = 0; j <= m; j++)            //第i行放入j个国王
            for (int s = 0; s < st.size(); s++) //遍历每一个合法状态s
                //s状态可以转化为哪些状态k
                for (int k = 0; k < head[s].size(); k++) {
                    //通过预处理结果，知道此状态st[s]使用了多少个国王
                    int c = cnt[st[s]];
                    if (c <= j)             //有点像背包问题，不能超过本次枚举的国王数量上限
                        f[i][j][s] += f[i - 1][j - c][head[s][k]];
                }
    //输出结果
    //在第n+1行中,摆放了m个国王,并且第n+1行的状态为0000时的状态即为总方案数,因为此时m个国王在1~i中
    printf("%lld", f[n + 1][m][0]);
    return 0;
}