状态压缩是设计dp状态的一种方式。

当普通的dp状态维数很多（或者说维数与输入数据有关），但每一维总量很少时，可以将多维状态压缩为一维来记录。

这种题目最明显的特征就是：都存在某一给定信息的范围非常小（在20以内），而我们在dp中所谓压缩的就是这一信息。

（或者是在做题过程中分析出了某一信息种类数很少）

我们来看个例子。

 

经典题

给出一个n*m的棋盘，要放上一些棋子，要求不能有任意两个棋子相邻。求方案数。

n<=100;

m<=8。

 

如果m固定的话可以设f[i][0/1][0/1]...[0/1]表示每一行每一列放不放

如果不是固定的呢？

我们发现后面的多个0/1可以看成一个二进制数

那我们不就可以用数字代替后面的维数吗？

f[i][s]->f[i+1][s’](s&s’==0)

 

你会发现这样记录很暴力，状态数是与m相关的指数级的，但同时也就是因为m小我们就确实可以这么做。

 

其实本质就是很暴力的记录状态，只不过利用了题目本身的特殊条件（这一维很小），使得我们并不会因此复杂度过高。

同时也就是说，如果题目本身没有这样一个较小的信息，就不能应用状态压缩。

状态压缩dp肯定是有一维是指数级的，这正是状态压缩的特点。

来看一道题：

P1896 [SCOI2005]互不侵犯

                  

 

  

 

这个题可以状压DP的很明显的标志就是数据范围

我们设f[i][j][k]表示当前在第i行，这一行及之前总共放了j个国王，当前的状态是k

那么我们只要枚举行，然后再枚举状态转移就可以了

怎么判断互不侵犯？

用位运算就可以了

注意最后答案不能光统计最后一行，因为不一定在最后一行才用完所有的国王

代码：

#include
     
      using namespace std;typedef long long ll;int n,king;ll f[10][100][2000];int s[2000],num[2000];int cnt;ll ans;inline void pre(){    int tot=(1<