状态压缩DP | 动态规划

参考《算法竞赛进阶指南》、AcWing题库

状态压缩DP

在 $0 \times 51$ 节 “线性 DP” 中, 我们提到, 动态规划的过程是随着 “阶段” 的增长, 在每个状态维度上不断扩展的。在任意时刻, 已经求出最优解的状态与尚末求出最优解的状态在各维度上的分界点组成了 DP 扩展的 “轮廓”。对于某些问题, 我们需要在动态规划的 “状态” 中记录一个集合, 保存这个 “轮廓” 的详细信息, 以便进行状态转移。若集合大小不超过 $N$, 集合中每个元素都是小于 $K$ 的自然数, 则我们可以把这个集合看作一个 $N$ 位 $K$ 进制数, 以一个 $\left[0, K^{N}-1\right]$ 之间的十进制整数的形式作为 DP 状态的一维。这种把集合转化为整数记录在 DP 状态中的一类算法, 被称为状态压缩动态规划算法。

$0 \times 01$ 节的例题 “最短 Hamilton 路径” 已经向读者展示了简单的状态压缩 DP 思想。在求解最短 Hamilton 路径时, 整个状态空间可看作 $N$ 维, 每维代表一个节点, 只有 0 (尚末访问) 和 1 (已访问) 两个值。我们可以想象 DP 的 “轮廓” 以 “访问过的节点数目” 为阶段, 从 $(0,0, \cdots, 0)$ 扩展到 $(1,1, \cdots, 1)$ 。为了记录当前状态在每个维度上的坐标是 0 还是 1 , 我们使用了一个 $N$ 位二进制数, 即 $\left[0,2^{N}-1\right]$ 之间的十进制整数存储节点的访问情况。另外, 为了知道最后经过的节点是哪一个, 我们把该节点编号作为附加信息, 也保存在 DP 的状态中。因此, 该状态压缩 DP 的状态数组就由大小分别为 $2^{N}$ 和 $N$ 的两个维度构成。

---

连通性状态压缩DP

---

291. 蒙德里安的梦想

题目描述

求把 $N \times M$ 的棋盘分割成若干个 $1 \times 2$ 的的长方形，有多少种方案。

例如当 $N=2，M=4$ 时，共有 $5$ 种方案。当 $N=2，M=3$ 时，共有 $3$ 种方案。

如下图所示：

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 $N$ 和 $M$。

当输入用例 $N=0，M=0$ 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

$1 \le N,M \le 11$

输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0 

输出样例：

1
0
1
2
3
5
144
51205 

算法分析

对于任意一种方案, 考虑以某一行为界, 把整个棋盘横着分成两半, 如下图所示。在上半部分最后一行中：

1. 每个灰色背景的部分都是一个坚着的 $1 * 2$ 长方形的 一半, 决定了下一行必须继续补全该长方形。

2. 其余部分对下半部分的分割方法没有影响。下一行既可以在连续两个位置安排一个横着的 $1 * 2$ 长方形, 也可以让某个位置作为一个坚着的 $1 * 2$ 长方形的一半。

   

综上所述, 我们可以把 “行号” 作为 DP 的 “阶段”, 把 “上半部分” 不断向下扩展, 直至确定整个棋盘的分割方法。为了描述上半部分最后一行的详细形态, 我们可以使用一个 $M$ 位二进制数, 其中第 $k(0 \leq k<M)$ 位为 1 表示第 $k$ 列是一个坚着的 $1 * 2$ 长方形的上面一半, 第 $k$ 位为 0 表示其他情况。

设 $F[i, j]$ 表示第 $i$ 行的形态为 $j$ 时, 前 $i$ 行分割方案的总数。 $j$ 是用十进制整数记录的 $M$ 位二进制数。

第 $i-1$ 行的形态 $k$ 能转移到第 $i$ 行的形态 $j$, 当且仅当:

1. $j$ 和 $k$ 执行按位与运算的结果是 0 。
   这保证了每个数字 1 的下方必须是数字 0 , 代表继续补全坚着的 $1 * 2$ 长方形。

2. $j$ 和 $k$ 执行按位或运算的结果的二进制表示中, 每一段连续的 0 都必须有偶数个。

   这些 0 代表若干个横着的 $1 * 2$ 长方形, 奇数个 0 无法分割成这种形态。

我们可以在 DP 前预处理出 $\left[0,2^{M}-1\right]$ 内所有满足 “二进制表示下每一段连续的 0 都有偶数个” 的整数, 记录在集合 $S$ 中。

$$F[i, j]=\sum_{j \& k=0} \sum_{\text {并且 } j \mid k \in S} F[i-1, k]$$

初值: $F[0,0]=1$, 其余均为 0 。
目标: $F[N, 0]$ 。
时间复杂度为 $O\left(2^{M} 2^{M} N\right)=O\left(4^{M} N\right)$ 。

int n, m;
long long f[12][1 << 11];
bool in_s[1 << 11];

int main()  {
	while (cin >> n >> m && n) {
		for (int i = 0; i < 1 << m; i++) {
			bool cnt = 0, has_odd = 0;
			for (int j = 0; j < m; j++)
				if (i >> j & 1) has_odd |= cnt, cnt = 0;
				else cnt ^= 1;
			in_s[i] = has_odd | cnt ? 0 : 1;
		}
		f[0][0] = 1;
		for (int i = 1; i <= n; i++)
			for (int j = 0; j < 1 << m; j++) {
				f[i][j] = 0;
				for (int k = 0; k < 1 << m; k++)
					if ((j&k) == 0 && in_s[j | k])
						f[i][j] += f[i - 1][k];
			}
		cout << f[n][0] << endl;
	}
}

Solution

1064. 小国王

题目描述

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

输入格式

共一行，包含两个整数 $n$ 和 $k$。

输出格式

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

数据范围

$1 \le n \le 10$,
$0 \le k \le n^2$

输入样例：

3 2 

输出样例：

16 

算法分析

分析1

算法构造

这道题目，根据数据范围，不难得出，这道题目考察的是状态压缩动态规划。

分析题目，我们可以得到如下信息。

1. 一个点的相邻八格，不可以有其他点。
2. 棋盘置点类型。

那么，我们接下来，思考两个流程。

1. 如何表示状态
2. 如何转移方程

表示状态

显然，题目给的条件，是国王总数是严格限制的，就是k个。

所以说，我们放置了多少个国王，是需要考虑的。

接着，根据棋盘类型的状态压缩动态规划的套路，每一行的状态，我们需要明白。

也就是每一行，哪些位置放了国王。

综上所述，我们可以得出，动态规划的状态表示。

$$f[i][j][s]为所有只摆在前i行，目前摆了j个国王，而且第i行的摆放状态为s$$

我们可以举一个例子

$$n=5 \\ f[1][2][20]表示第一行，已经摆了两个国王，摆在左边第一个，和左边第三个 \\ (20)_{10}=(10100)_{2}$$

状态转移

在这里，状态之间的转移，必然要满足，国王之间不会相互攻击到，那么我们进行分析。

两个国王，如果他们存在，直接靠近（上下左右）或者简介靠近（两斜对角），那么显然是不合法的。

因此，转换成为状态理解。

对于一个状态集合而言，显然不能存在相邻的1.

$$101 (可以) \quad 两个国王有间隔\\ 110 (不可以) \quad 国王1和国王2相邻，可以相互攻击\\$$

因为这会导致，左右两个国王相邻，然后发起攻击。

而且，对于上下两行而言，不能有共同的一位有1

$$101 \\ 101$$

因为这会导致，上下两个国王相邻，然后发起攻击。

我们讨论完了，上下左右，接下来是最难的两斜对角。

$$我们设，第i行的状态为a，第i+1行状态为b$$

那么

$$S=a 或 b \ 也就是S=a|b$$

是不可以存在，有相邻的1的。

$$a=100 \\ b=010 \\ S=110 \\$$

因此这会导致，两斜对角国王相互攻击。

综上所述，我们得到集合转移的约束条件。

分析2

这种 棋盘放置类 问题，在没有事先知道一些特定 性质 的情况下来做，都会想到 爆搜

本题的数据规模，也是向着 爆搜 去设置的

如果我们直接 爆搜，则 时间复杂度 为 $O(2^{n^2})$ 是会超时的，因此会想到用 记忆化搜索 来进行优化

考虑一下如何进行 动态规划

由于在第 $i$ 层放置国王的行为，受到 $i-1$ 层和 $i+1$ 层以及 $i$ 层的状态影响

那么我们就可以规定从上往下枚举的顺序，这样考虑第 $i$ 层状态时，只需考虑 $i-1$ 层的状态即可

于是乎我们可以考虑把层数 $i$ 作为动态规划的 阶段 进行 线性DP

而第 $i$ 阶段需要记录的就是前 $i$ 层放置了的国王数量 $j$，以及在第 $i$ 层的 棋盘状态 $k$

这里先分析一下，哪些 棋盘状态 是合法的，哪些 棋盘状态的转移 是合法的

合法的棋盘状态

如上图所示，绿色方块为摆放国王的位置，红色方块为王的 攻击范围

只要任意王之间只要 不相邻，就是 合法的状态

合法的棋盘转移状态

如上图所示，绿色方块为摆放国王的位置，红色方块为王的 攻击范围

只要任意王的 纵坐标不相邻，就是 合法的转移状态

我们可以用 二进制 来表示当前的状态

怎么用二进制表示状态？

若(state >> i) == 1 则表示在当前状态中，第 $k(0\le i\lt n)$ 个位置放置了国王（下标从 $0$ 开始）

再举一个简单的例子，见下图：

用二进制表示该状态，就是 $(00100010)_b$

状态表示—集合$f_{i,j,k}:$ 考虑前 $i$ 层的棋盘，前 $i$ 层放置了 $j$ 个国王，且第 $i$ 层状态是 $k$ 的方案
状态表示—属性$f_{i,j,k}:$ 方案的总数 $Sum$
状态计算—$f_{i,j,k}:$

$$f_{i,j,k} = \sum_{pre} f_{i-1,j-cnt_k,pre}$$

其中$pre$是枚举的能够与$k$合法存在于相邻行中的所有状态，$cnt_k$表示状态$k$中的国王数量

初始状态： $f_{0,0,0}$
目标状态： $f_{n,K,st} \quad(其中st为所有合法状态)$

这样直接做，时间复杂度是 $O(n^3 K 2^n 2^n)$ 是会超时的

但是我们可以通过预处理所有的 合法状态，以及合法的 相邻转移状态，以及 合法状态 摆放的国王数量

因为虽然状态很多，但是 合法状态 并不多， 合法的转移状态 更不多

目标状态优化思路

我们可以很轻易的观察到，如果当前层的一个棋子都不摆，即$state = (000000)_b$

那么所有 合法的状态 都是该状态的 合法转移状态

翻译成白话就是：只要这层不摆东西，则上一层 只要合法，那一定可以转移到这一层的这个状态

因此我们可以把目标状态设为 $f_{n+1,K,0}$

该状态表示 考虑前 $n+1$ 层的棋盘，前 $n+1$ 层放置了 $K$ 个国王，且第 $n+1$ 层什么也没放的方案

根据我们之前提到的 状态转移 可知，该状态会把所有到第 $n$ 层的 合法状态 都转移到自己身上

这样最后我们就 不需要额外枚举所有的目标状态 了

Solution

#include <iostream>
#include <vector>
using namespace std;

const int N = 12, M = 1 << 10, K = 110;

int n, m;
long long f[N][K][M];
vector<int> valid, convert[M];
int cnt[M]; 

bool check(int state) {//检查当前状态是否有效
  for (int i = 0; i < n; ++i) 
    if ((state >> i & 1) && (state >> i + 1 & 1)) return false;
  return true;
  //或者 return !(state & state >> 1);  
  
}

int count(int state) {//计算当前状态中1的个数
  int cnt = 0;
  for (int i = 0; i < n; ++i) cnt += state >> i & 1;
  return cnt;
}

void pre() {//预处理
  for (int st = 0; st < (1 << n); ++st) {//预处理出有效状态
    if (check(st)) {
      valid.push_back(st);
      cnt[st] = count(st);
    }
  }
  
  for (auto a : valid) {//预处理出当前状态可以转向的状态
    for (auto b : valid) {
      if ((a & b) == 0 && check(a | b)) convert[a].push_back(b);
    }
  }
}
int main() {
  cin >> n >> m;
  
  pre(); 
    
  f[0][0][0] = 1;
  for (int i = 1; i <= n + 1; ++i) {//i = n + 1 为了输出答案方便
    for (int j = 0; j <= m; ++j) {
      for (auto a : valid) {
        if (j >= cnt[a]) {
          //这里可以用滚动数组优化
          for (auto b : convert[a]) f[i][j][a] += f[i - 1][j - cnt[a]][b];
        }
      }
    }
  }
  
  cout << f[n + 1][m][0];
}

---

327. 玉米田

题目描述

农夫约翰的土地由 $M \times N$ 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第 $1$ 行包含两个整数 $M$ 和 $N$。

第 $2..M+1$ 行：每行包含 $N$ 个整数 $0$ 或 $1$，用来描述整个土地的状况，$1$ 表示该块土地肥沃，$0$ 表示该块土地不育。

输出格式

输出总种植方法对 $10^8$ 取模后的值。

数据范围

$1 \le M,N \le 12$

输入样例：

2 3
1 1 1
0 1 0 

输出样例：

9 

算法分析

本题需要额外处理的，是给定的 $01$ 矩阵里存在着的不能放置棋子的位置

我们用二进制存储的状态 $state$ 中，使用 $1$ 表示在该位置放置棋子，$0$ 表示在该位置没有棋子

因此我们可以把矩阵每一层的状态也用二进制来压缩存储，且用 $0$ 表示该位置能放棋子，$1$ 表示不能放

这样，只需把枚举的状态 $state_{cur}$ 与这一层的状态 $state_{g_i}$ 做 & 运算

1. 结果为0，表示 放置棋子 的位置没有与 不能放置棋子 的位置重叠，则该状态 合法
2. 结果不为0，表示 放置棋子 的位置与 不能放置棋子 的位置发生重叠，则该状态 不合法

具体如下图所示：

状态表示—集合$f_{i,j}:$ 考虑前 $i$ 层，且第 $i$ 层状态是 $j$ 的方案
状态表示—属性$f_{i,j}:$ 方案的总数 $Sum$
状态计算—$f_{i,j}:$

$$f_{i,j} = \sum_{pre} f_{i-1,pre}$$

其中$pre$是枚举的能够与$j$合法存在于相邻行中的所有状态

Solution

#include <iostream>
#include <vector>
using namespace std;

const int N = 15, M = 1 << 12, mod = 1e8;

int f[2][M];
vector<int> valid, convert[M];
int g[N], n, m;

bool check(int state) {
  return !(state & state << 1);
}

void pretreat() {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      int t;
      cin >> t;
      //或者g[i] += !t << j , j from m - 1 to 0
      g[i] = g[i] * 2 + !t;
    }
  }

  for (int st = 0; st < (1 << m); ++st) 
    if (check(st)) valid.push_back(st);
  
  for (auto a : valid) 
    for (auto b : valid) 
      if ((a & b) == 0) convert[a].push_back(b);
}

int main() {
  cin >> n >> m;
  
  pretreat();
  
  f[0][0]= 1;
  for (int i = 1; i <= n + 1; ++i) {
    for (auto a : valid) {
      f[i & 1][a] = 0;//使用滚动数组时，这里注意清零
      if (g[i] & a) continue;
      for (auto b : convert[a]) f[i & 1][a] = (f[i & 1][a] + f[(i - 1) & 1][b]) % mod;
    }
  }
  cout << f[(n + 1) & 1][0];
}

---

292. 炮兵阵地

题目描述

司令部的将军们打算在 $N \times M$ 的网格地图上部署他们的炮兵部队。

一个 $N \times M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。

从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入格式

第一行包含两个由空格分割开的正整数，分别表示 $N$ 和 $M$；

接下来的 $N$ 行，每一行含有连续的 $M$ 个字符(P 或者 H)，中间没有空格。按顺序表示地图中每一行的数据。

输出格式

仅一行，包含一个整数 $K$，表示最多能摆放的炮兵部队的数量。

数据范围

$N \le 100,M \le 10$

输入样例：

5 4
PHPP
PPHH
PPPP
PHPP
PHHP 

输出样例：

6 

算法分析

本题与上一题类似, 都是在矩形网格中放置图形的问题。上一题是求放满 $1 * 2$ 的 长方形的方案数, 本题则是求最多能放多少个 “十字形状”, 并且每个 “十字” 的中心 都不被其他 “十字” 覆盖。因此, 我们还是采用按 “行号” 为阶段的 DP 方法。

解法一

因为每个位置能否放置炮兵与它上面两行对应位置上是否放置炮兵有关, 所以在 向第 $i$ 行的状态转移时, 需要知道第 $i-1$ 行和第 $i-2$ 行的状态。我们把每一行的 状态看作一个 $M$ 位二进制数, 用一个 $0 \sim 2^{M}-1$ 之间的十进制整数存储, 其中第 $p(0 \leq p<M)$ 位为 1 表示该行第 $p$ 列放置了炮兵, 为 0 则表示没有放置炮兵。

我们在 DP 前预处理出集合 $S$, 存储 “相邻两个 1 的距离不小于 3 ” 的所有 $M$ 位二 进制数, 这些二进制数代表每一行中两个炮兵的距离不能小于 3 。

设 $\operatorname{count}(x)$ 表示 $M$ 位二进制数 $x$ 中 1 的个数。

设 $\operatorname{valid}(i, x)$ 表示 $M$ 位二进制数 $x$ 属于集合 $S$, 并且 $x$ 中的每个 1 对应在地图 第 $i$ 行中的位置都是平原。

设 $F[i, j, k]$ 表示第 $i$ 行压缩后的状态为 $j$, 第 $i-1$ 行压缩后的状态为 $k$ 时, 前 $i$ 行最多能摆放多少个炮兵。

$$\begin{aligned} F[i, j, k] = \begin{cases} \mathop{\max}\limits_{j \& l=0}\{F[i-1, k, l]\}+\operatorname{count}(j) \quad &\text {如果 valid }(i, j), \text { valid }(i-1, k) \text { 并且 } j \& k=0 \\ -\infty &否则 \end{cases} \end{aligned}$$

初值: $F[0,0,0]=0$, 其余为负无穷。

目标: $\mathop{\max \{F[N, j, k]\}}\limits_{j \& k=0, \text { valid }(N, j, j) ,\text { valid }(N-1, k)}$

虽然 $M$ 位二进制数有 $2^{M}$ 个, 但只有集合 $S$ 中的数才可能是合法状态。通过写程 序预处理可以发现, 事实上 $S$ 集合非常小, 仅包含不到 100 个数。我们可以对集合 $S$ 中的数离散化, 只对这些状态进行存储和遍历。时间和空间复杂度均为 $O\left(N|S|^{3}\right)$ 。

解法二

上一个解法状态压缩以后的规模本来是 $O\left(N * 4^{M}\right)$, 我们利用题目的特殊性排除掉了不合法的状态, 才使解法变得高效。接下来我们再介绍一种更通用的做法。这种做法仍以 “行” 作为动态规划的阶段, 但用更高进制的状态压缩代表一行的状态, 从而区分网格中不同位置的不同属性。

根据题意, 一个格子放置炮兵以后, 该格子上下两行的同一列都不能再放置炮兵。可以用数字 2 表示放置炮兵的格子, 规定 2 的下面必须是 1,1 的下边必须是 0, 只有 0 的下边可以放置新的炮兵。在炮兵不会误伤的情况下, 每个 “十字” 攻击范围形如:

$$\leq 1 \leq 1 \quad \begin{gathered} \leq 1 \\ 0 \\ 2 \\ 1 \\ 0 \end{gathered} \leq 1 \leq 1$$

把每行的状态压缩为一个 $M$ 位三进制数, 用 $0 \sim 3^{M}-1$ 之间的十进制整数存储。 设 $F[i, j]$ 表示第 $i$ 行压缩后的状态为 $j$ 时, 前 $i$ 行最多能放多少个炮兵, 并且前 $i$ 行的炮兵不会误伤。状态规模为 $O\left(N * 3^{M}\right)$, 不会超过内存限制。

对于每个已经求出的合法的 $F[i, j]$, 我们考虑它能转移到哪些状态。这等价于依次考虑第 $i+1$ 行的每个位置填写什么数字。需要满足四个条件:

1. 当第 $i$ 行第 $j$ 列为 2 时, 第 $i+1$ 行第 $j$ 列必须填 1 。
2. 当第 $i$ 行第 $j$ 列为 1 时, 第 $i+1$ 行第 $j$ 列必须填 0 。
3. 山地格子不能填 2 。
4. 一个格子填 2 以后, 它右边的两个格子不能再填 2 。

像本题这种状态表示比较复杂、冗余较多的题目, 我们不一定非要写出确切的状态转移方程。可以通过深度优先搜索 (DFS), 在保证上述四个条件的前提下, 搜索第 $i+1$ 行的每个位置填写什么数字。在到达搜索边界时 ( $M$ 个位置都填完), 就得到了一个 状态 $k$, 从而可以从 $F[i, j]$ 转移到 $F[i+1, k]$ 。总而言之, 整个动态规划算法使用三进制压缩的状态表示, 以 “行号” 为阶段, 在相邻两行之间使用 DFS 进行转移。

上面两道例题都是 “填充网格图形” 类的题目, 并且填充的图形仅与相邻的若干行有关, 容易按照 “行号” 划分阶段, 从而应用状态压缩动态规划算法。有些更为复杂 的题目, 填充的图形与整个网格有关, 就需要进一步提炼动态规划过程中 “轮廓” 的特点。这超出了我们的讨论范围, 学有余力的读者可以自行查阅论文, 学习 “基于连通性的状态压缩动态规划” (简称 “插头 DP”)。

基于连通性的状态压缩动态规划问题

Solution

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 1 << 10;

int n, m;
int f[2][M][M];
int g[N], cnt[M];
vector<int> valid, convert[M];

bool check(int st) {
  return !((st & st >> 1) | (st & st >> 2));
}

int count(int st) {
  int cnt = 0;
  for (int i = 0; i < m; ++i) cnt += st >> i & 1;
  return cnt;
}


void pretreat() {
  for (int st = 0; st < (1 << m); ++st) 
    if (check(st)) {
      valid.push_back(st);
      cnt[st] = count(st);
    }
  
  for (auto cur : valid) {
    for (auto pre : valid) {
      if ((cur & pre) == 0) convert[cur].push_back(pre);
    }
  }
  
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      char c;
      cin >> c;
      g[i] += (c == 'H') << (m - j);
    }
  }
  
  pretreat();
  
  for (int i = 1; i <= n + 2; ++i) {
    for (auto cur : valid){
      if (g[i] & cur) continue;
      for (auto pre1 : convert[cur]) {
        f[i & 1][cur][pre1] = 0;
        if (g[i - 1] & pre1) continue;
        for (auto pre2 : convert[pre1]) {
          if (cur & pre2) continue;
          f[i & 1][cur][pre1] = max(f[i & 1][cur][pre1], f[i - 1 & 1][pre1][pre2] + cnt[cur]);
        }
      }
    }
  }
  
  cout << f[n + 2 & 1][0][0];
  
}

---

集合类状态压缩DP

---

91. 最短Hamilton路径

题目描述

给定一张 $n$ 个点的带权无向图，点从 $0 \sim n-1$ 标号，求起点 $0$ 到终点 $n-1$ 的最短 Hamilton 路径。

Hamilton 路径的定义是从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 $n$。

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离（记为 $a[i,j]$）。

对于任意的 $x,y,z$，数据保证 $a[x,x]=0，a[x,y]=a[y,x]$ 并且 $a[x,y]+a[y,z] \ge a[x,z]$。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

$1 \le n \le 20$
$0 \le a[i,j] \le 10^7$

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0 

输出样例：

18 

算法分析

Solution

---

524. 愤怒的小鸟

题目描述

Kiana 最近沉迷于一款神奇的游戏无法自拔。

简单来说，这款游戏是在一个平面上进行的。

有一架弹弓位于 $(0,0)$ 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟， 小鸟们的飞行轨迹均为形如 $y=ax^2+bx$ 的曲线，其中 $a,b$ 是 Kiana 指定的参数，且必须满足 $a<0$。

当小鸟落回地面（即 $x$ 轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有 $n$ 只绿色的小猪，其中第 $i$ 只小猪所在的坐标为 $(x_i,y_i)$。

如果某只小鸟的飞行轨迹经过了 $(x_i, y_i)$，那么第 $i$ 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；

如果一只小鸟的飞行轨迹没有经过 $(x_i, y_i)$，那么这只小鸟飞行的全过程就不会对第 $i$ 只小猪产生任何影响。

例如，若两只小猪分别位于 $(1,3)$ 和 $(3,3)$，Kiana 可以选择发射一只飞行轨迹为 $y=−x^2+4x$ 的小鸟，这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个这个游戏。

这些指令将在输入格式中详述。

假设这款游戏一共有 $T$ 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。

由于她不会算，所以希望由你告诉她。

注意:本题除 NOIP 原数据外，还包含加强数据。

输入格式

第一行包含一个正整数 $T$，表示游戏的关卡总数。

下面依次输入这 $T$ 个关卡的信息。

每个关卡第一行包含两个非负整数 $n,m$，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。

接下来的 $n$ 行中，第 $i$ 行包含两个正实数 $(x_i,y_i)$，表示第 $i$ 只小猪坐标为 $(x_i,y_i)$，数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果 $m=0$，表示 Kiana 输入了一个没有任何作用的指令。

如果 $m=1$，则这个关卡将会满足：至多用 $⌈n/3+1⌉$ 只小鸟即可消灭所有小猪。

如果 $m=2$，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 $⌊n/3⌋$ 只小猪。

保证 $1 \le n \le 18，0 \le m \le 2，0<x_i,y_i<10$，输入中的实数均保留到小数点后两位。

上文中，符号 $⌈c⌉$ 和 $⌊c⌋$ 分别表示对 $c$ 向上取整和向下取整，例如 ：$⌈2.1⌉=⌈2.9⌉=⌈3.0⌉=⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3$。

输出格式

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。

数据范围

输入样例：

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00 

输出样例：

1
1 

算法分析

首先分析一下我们用弹弓发射的子弹的轨迹有哪些特点：$y=ax^2+bx+c$

1. 一条经过原点的抛物线 $c = 0$
2. 抛物线的开口朝下 $a<0$

这样抛物线方程就可以设为：$y=ax^2+bx$

方程中有两个参数 $a$ 和 $b$，因此我们可以用具体两个点的坐标来唯一的确定一条 抛物线

参数的计算公式如下：

$${\begin{cases} y_1 = ax_1^2 + bx_1 \\ y_2 = ax_2^2 + bx_2\end{cases}} \quad \Rightarrow \quad {\begin{cases} a = \dfrac{\dfrac{y_1}{x_1} - \dfrac{y_2}{x_2}}{x_1 - x_2}\\ b = \dfrac{y_1}{x_1} - ax_1\end{cases}}$$

于是我们就可以预处理出最多 $n^2$ 条抛物线，然后用这些抛物线对 点集 进行覆盖即可

此时问题变成了经典的“重复覆盖问题”，即给定01矩阵，要求选择尽量少的行，将所有列覆盖住。这里标准做法是使用 Dancing Links。

但由于 $n<=18$，因此可以直接使用状态压缩DP求解，代码更简单。

f[i] 表示当前已经覆盖的列是i时的最小行数。

转移时随便找到当前未被覆盖的某一列 $x$，然后枚举所有包含 $x$ 的行j来选择即可。

即：f[i | j] = min(f[i | j], f[i] + 1)。

用已知两点预处理出来的抛物线一定要满足合法（即$a<0$）

然后对于两点构成的抛物线，我们还要处理出他穿过的其他的点

这样预处理的时间复杂度就是 $O(n^3)$

---

到此处位置，我们就把问题转化为， 重复覆盖问题 （大家可以用搜索优化 Dancing Links 处理该问题 ）

本题解采用 状态压缩DP 来完成

状态表示—集合$f_i$：当前点集覆盖状态为 $i$ 的方案（$i$是采用二进制压缩存储的点集覆盖状态）
状态表示—属性$f_i$：方案用的抛物线数量最少 $Min$
状态表示—计算$f_i$：

$$f_{ne} = min(f_i) + 1$$

其中 $ne$ 是状态 $i$ 枚举到新抛物线，并进行覆盖以后生成的新状态 $ne$

初始状态 ：$f_0$
目标状态 ：$f_{1\cdots 1}$

时间复杂度：

1. 预处理 $O(n^3)$
2. 状压DP $O(n2^n)$

Solution

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const double eps = 1e-6;
const int N = 20, M = 1 << 18;

int n, m;
double x[N], y[N];
int path[N][N]; 
int f[M];

int check(double a, double b) {
  if (fabs(a - b) < eps) return 0; // a == b
  if (a < b) return -1;
  if (a > b) return 1;
}

void pretreat() {
  memset(path, 0, sizeof path);
  for (int i = 1; i <= n; ++i) {
    path[i][i] = 1 << (i - 1);//由点(0,0) (x[i], y[i]) 确定的抛物线，包含点i
    for (int j = 1; j <= n; ++j) {
      if (check(x[i], x[j]) == 0) continue;//点i和点j是同一点，跳过
      double a = (y[i] / x[i] - y[j] / x[j]) / (x[i] - x[j]);
      if (check(a, 0) >= 0) continue;//必须有a < 0，否则跳过
      double b = y[i] / x[i] - a * x[i];
      //预处理由点i和点j确定的抛物线，可以经过哪些点
      int st = 0;//初始化
      for (int k = 1; k <= n; ++k) {
        //如果点k在由点i和点j确定的抛物线上，则把点k加入
        if (check(y[k], a * x[k] * x[k] + b * x[k]) == 0) {
          st += 1 << (k - 1);//加入点k
        }
      }
      path[i][j] = st;//更新最终由点i和点j确定的抛物线可以经过的路线点
    }
  }
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
    
    pretreat();//预处理
    
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    //枚举当前状态
    for (int curst = 0; curst + 1 < 1 << n; ++curst) {
      //找到第一个没有被覆盖的点
      int t1 = 0;
      for (int i = 1; i <= n; ++i) {
        if (curst >> (i - 1) & 1) continue;//已被覆盖，跳过
        t1 = i;//找到第一个没被覆盖的点
        break;//已找到，跳出
      }
      //要新增抛物线覆盖点t1，枚举新抛物线
      for (int t2 = 1; t2 <= n; ++t2) {//点t1,t2共同确定新抛物线
        int newst = path[t1][t2];//新抛物线可以覆盖的点
        int nextst = curst | newst;//加上这条新抛物线一共可以覆盖的点，进入下一个状态
        //如果采取当前状态+新抛物线，则下一状态需要的抛物线条数 + 1
        f[nextst] = min(f[nextst], f[curst] + 1);
      }
    }
    
    cout << f[(1 << n) - 1] << endl;
  }
}

---

529. 宝藏

题目描述

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 $n$ 个深埋在地下的宝藏屋，也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。

但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。

已经开凿出的道路可以任意通行不消耗代价。

每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。

另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是：

这条道路的长度 $×$ 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

输入格式

第一行两个用空格分离的正整数 $n$ 和 $m$，代表宝藏屋的个数和道路数。

接下来 $m$ 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为 $1 \sim n$），和这条道路的长度 $v$。

输出格式

输出共一行，一个正整数，表示最小的总代价。

数据范围

$1 \le n \le 12$,
$0 \le m \le 1000$,
$v \le 5*10^5$

输入样例：

4 5 
1 2 1 
1 3 3 
1 4 1 
2 3 4 
3 4 1 

输出样例：

4 

注意

本题数据有加强，前二十个测试点为 NOIP 官方数据，后三个测试点为加强数据。

算法分析

Solution