NOIP专题复习（三） 状压DP学习笔记 - LiRewriter的博客 - CSDN博客

NOIP专题复习（三） 状压DP学习笔记 - LiRewriter的博客 - CSDN博客

我觉得学普通的DP已经救不了我了。
发觉似乎NOIP状压蛮裸的（flag立的飞起），于是学一波。

其实在下作为一只蒟蒻，认为状压DP属于很好理解但不太好写的类型。
还是从经典例题互不侵犯开始。

luogu1896 互不侵犯

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
1 <=N <=9, 0 <= K <= N * N

在下大致将学习这道题做法步骤拆分如下。
1，数据范围是识别状压DP的标志。
这个数据范围，一般来说是状压DP。

2，位运算是进行状压DP的主力武器。
很多教程都会直接讲一下四个运算符是什么意思，然后直接上代码。
在下觉得有点不太友好啊orz。毕竟大家都知道这是什么意思，只是不会写而已。
首先对于这道题，用到的位运算大致解析如下：
假设现在某一行状态为i，i的对应的二进制数，某一位是1表示这一位放棋子，是0表示不放。

Read full article from NOIP专题复习（三） 状压DP学习笔记 - LiRewriter的博客 - CSDN博客