状态压缩动态规划是一类特殊的动态规划，通常有一维用来表示一个二进制状态。状态压缩，顾名思义，就是把原来要一个bool数组表示状态压缩到一个int变量里。围绕状压DP，我们将介绍它的前世今生，领略状压DP的特点、技巧、应用。

Part 1 特点

状压DP的最显著特点就是n一般不会超过20，这样你才能状压啊。

其次，状压DP经常会被用来解决类似于全排列的问题，这里以2008年宁波市初中组的导游一题为例：

宁波市的中小学生们在镇海中学参加程序设计比赛之余，热情的主办方邀请同学们参观镇海中学内的各处景点，已知镇海中学内共有n处景点。现在有n位该校的学生志愿承担导游和讲解任务。每个学生志愿者对各个景点的熟悉程度是不同的，如何将n位导游分配至n处景点，使得总的熟悉程度最大呢？要求每个景点处都有一个学生导游。(1≤n≤17)

如果我们用一个数列来表示每一种方案的话，所有数列大概是这个样子的：（数列中的第i个数表示第i个人去的景点编号）

1 2 3 4 5 6

1 2 3 4 6 5

1 2 3 5 4 6

1 2 3 5 6 4

1 2 3 6 4 5

1 2 3 6 5 4

1 2 4 ......

可以看出，这是一个全排列，这是为什么呢？从组合数学的角度解释所有方案是1~n的全排列：A(n,n)

好像很有趣的样子欸。我们先来写一个DFS吧。

bool b[maxn]void dfs(int t, int s){    if (t>n){        if (s>ans) ans=s;        return;    }    for (int i = 1; i <= n; i++)        if (!b[i]){            b[i]=true;            dfs(t+1,s+a[t][i]);            b[i]=false;        }}

众所周知，有b[]这样的全局数组的DFS是不能记忆化的，因为b[]这个数组不可能作为一个状态。但是，状压DP为我们提供了这一可能。

bool类型在C++和Pascal中都使用了整整1个字节（Byte），也就是8位二进制(bit)，其实需要这么多，1位二进制就足够表示一个bool了，所以我们可以把最多30位二进制（bit）压到一个int（32位）中去。

我们用f[i][sta]表示前i个学生去了状态为sta的景点，那么 \[f[i][sta]=max\{f[i-1][sta-2^{j-1}]+w[i][j]\}\]

又发现sta中1的个数就是i，欧耶，有可以砍掉1维！

\[f[sta]=max\{f[sta-2^{j-1}]+w[num[sta]][j]\}\]

（num[sta]表示sta中1的个数，可以预处理出来）

简明扼要的代码：

#include
    
     using namespace std; int n,w[18][18];int num[1<<18],f[1<<18]; int main(){    scanf("%d", &n);    for (int i=1; i<=n; i++)        for (int j=1; j<=n; j++) scanf("%d", &w[i][j]);    num[0]=0; num[1]=1;    for (int sta=2; sta<(1<
     
      >1]+(sta&1);    f[0]=0;    for (int sta=1;sta<(1<
     
    

Part 2 技巧

状压DP有一个独门技巧——预处理转移。

在状压DP中，我们会经常碰到很多很多没有意义的状态和没有意义的转移，这些没有意义的东西浪费着宝贵的内存和宝贵的时间，我们得想个办法把它们从合法状态中分离出来。

现有n*m的一块地板，需要用1*2的砖块去铺满，中间不能留有空隙。问这样方案有多少种。多组数据，以n=0,m=0结束。 （1<=n, m<=11)

一看就很难，对不对？不要慌张，我们可以用状压大法。

\[f[i][sta] 表示铺了前i行，第i行对第i+1行的影响是sta.\]

为什么要这样定状态讷？

我们发现：1*2的砖块只有2种摆放方式，横着和竖着。

如果横着放，对后面一行没有影响；如果竖着放，对后一行会产生影响。

所以，状态转移方程是：

\[f[i][sta]=\Sigma f[i-1][sta'] \quad (sta'->sta是合法的)\]

那么，什么样的转移才是合法的呢？在这里，我们需要用到按位分析的方法：对于\(sta\)和\(sta'\)的每一位，共有4种情况：

sta	sta'	是否合法
1	1	false
1	0	true
0	1	true
0	0	true

如果我们在DP时枚举每种状态\(sta\)和\(sta'\)，判断转移是否合法，时间复杂度是\(O(n*4^n)\).如果你按一下计算器，发现时间是5000W左右，AC！

可是，抱着精益求精的态度，而且好像有多组数据，这还不够优秀。有必要枚举\(4^n\)种转移吗？我们已经知道只有\(3^n\)是合法的，为什么还要枚举\(4^n\)种转移呢？

So,我们可以预处理合法转移，再进行DP，时间复杂度为\(O(n*3^n)\).很优秀。

简明扼要的代码：

#include
    
     using namespace std; int n,m,tot;int change[200005][2];long long f[12][200005]; void dfs(int pos,int from,int to){    if (pos==m){        change[++tot][0]=from;        change[tot][1]=to;        return;     }     if ((from>>pos)&1) dfs(pos+1,from,to);    else{        dfs(pos+1,from,to+(1<
     
      >pos+1)&1)==0)) dfs(pos+2,from,to);    }} void resetchange(){    for (int sta=0; sta<(1<
     
    

Part 3 应用

好累啊，不想写题目大意了，放个吧。

再来个

就这样。