#### 分析
由于 $n$ 比较小，且每个村庄只会经过 1 次，可以通过状压将经过村庄的状态通过整数的二进制表示。因为转移时增加的路程与最后所在的村庄有关，还需要再开一维记录最后到达的村庄。
#### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 22;
const int NN = 1 << N;
// G存图，dp[i][j]表示状态为 i 时，最后到达的村庄是 j
int n, G[N][N], dp[NN][N], ans = 2e9;
int main () {
ios::sync_with_stdio (0);
cin.tie (0); cout.tie (0);
memset (G, -1, sizeof G);
cin >> n;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++)
cin >> G[i][j];
}
memset (dp, 0x3f, sizeof dp);
// 初始在村庄 1
dp[1][1] = 0;
// 枚举状态
for (int i = 0; i < (1 << n); i ++) {
// 枚举新的村庄
for (int j = 1; j <= n; j ++) {
// 如果新村庄已经到过，继续遍历
if (i & (1 << (j - 1))) continue;
int now = i | (1 << (j - 1));
// 枚举最后到达的村庄
for (int w = 1; w <= n; w ++) {
// 最后的村庄必须在状态中
if ((i & (1 << (w - 1))) == 0) continue;
if (!G[w][j]) continue;
// 转移
dp[now][j] = min (dp[now][j], dp[i][w] + G[w][j]);
}
}
}
// 获取答案
for (int i = 1; i <= n; i ++)
if (G[i][1])
ans = min (ans, dp[(1 << n) - 1][i] + G[i][1]);
cout << ans;
return 0;
}
```
### [P1896 [SCOI2005] 互不侵犯](https://www.luogu.com.cn/problem/P1896)
#### 题意
求在 $N \times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。
$1 \le N \le 9$，$0 \le K \le N\times N$。
#### 分析
考虑通过整数的二进制描述棋盘一行上的信息，每次枚举第 $i$ 行和第 $i - 1$ 行的情况，符合题意就进行转移。
#### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e3 + 5;
int n, k, c[N], d[N], dp[10][1 << 10][105];
// dp[i][j][k] 意为在第 i 行情况是 j 时放了 k 个王的情况数
signed main () {
cin >> n >> k;
int full = (1 << n) - 1;
// 预处理出同一行内的合法情况
int cnt = 0;
for (int i = 0; i <= full; i ++) {
if ((i & (i << 1)) || (i & (i >> 1))) continue;
c[++ cnt] = i;
int _i = i;
while (_i) {
if (_i % 2 == 1) d[i] ++;
_i /= 2;
}
}
dp[0][0][0] = 1;
// 枚举行
for (int i = 1; i <= n; i ++) {
int s, t;
// 枚举第 i 行
for (int j = 1; j <= cnt; j ++) {
s = c[j];
// 枚举第 i - 1 行
for (int w = 1; w <= cnt; w ++) {
t = c[w];
if (((s << 1) | (s >> 1) | s) & t) continue;
if (i == 1 && t != 0) continue;
// 共放了 y 个国王
for (int y = 0; y <= k; y ++)
if(y - d[s] >= 0)
dp[i][s][y] += dp[i - 1][t][y - d[s]];
}
}
}
// 统计答案
int ans = 0;
for (int i = 1; i <= cnt; i ++)
ans += dp[n][c[i]][k];
cout << ans;
return 0;
}
```
### [P3694 邦邦的大合唱站队](https://www.luogu.com.cn/problem/P3694)
#### 题意
$N$ 个偶像排成一列，他们来自 $M$ 个不同的乐队。重新安排队列，使来自同一乐队的偶像连续的站在一起。重新安排的办法是，让若干偶像出列（剩下的偶像不动），然后让出列的偶像一个个归队到原来的空位，归队的位置任意。求最少让多少偶像出列？
$1 \le N \le 10 ^ 5, M \le 20$。
#### 分析
由于 $M \le 20$，比较小，可以状压 $M$，状态为 $1$ 就表示当前乐队的所有偶像已经排列完毕，又因为重新排列的方式是插空位，考虑用前缀和记录人数来判断当前的位置有几个人不需要移动。
#### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 22;
const int MM = 1 << M;
int n, m, a[N], p[N][M], dp[MM], cnt[M];
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
cnt[a[i]] ++;
// 前缀和
// 前 i 个位置 j 乐队的人数
for (int j = 1; j <= m; j ++)
p[i][j] = p[i - 1][j] + (j == a[i]);
}
memset (dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int i = 0; i < (1 << m); i ++) {
// if (dp[i] > 1e8) continue;
int sum = 0;
// 通过算人数确定当前位置
for (int j = 1; j <= m; j ++)
if (i & (1 << (j - 1))) sum += cnt[j];
for (int j = 1; j <= m; j ++) {
if (i & (1 << (j - 1))) continue;
int now = i | (1 << (j - 1));
// 进行转移
dp[now] = min (dp[now], dp[i] + cnt[j] - p[sum + cnt[j]][j] + p[sum][j]);
}
}
cout << dp[(1 << m) - 1];
return 0;
}
```
### [P3092 [USACO13NOV] No Change G](https://www.luogu.com.cn/problem/P3092)
#### 题意
FJ 有 $K$ 个硬币，面值的范围是 $[1,10^8]$。他想按顺序买 $N$ 个物品，第 $i$ 个物品价格是 $c_i$。购买时，FJ 可以随时停下用 $1$ 个硬币付款，购买上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付），但是，商场不会找零。
求最多剩下多少钱。如果无法完成购买，输出 $−1$。
$1 \le N \le 10 ^ 5, 1 \le K \le 16$。
#### 分析
状压 $K$ 是否已经被使用，$dp_i$ 记录状态 $i$ 最多买到那件物品，在前缀和上二分查找最多能够买到那件物品。
#### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int K = 20;
const int KK = 1 << K;
int n, k, a[N], b[K], dp[KK], p[N], q[KK], ans = 2e9, sum;
int main () {
cin >> k >> n;
for (int i = 1; i <= k; i ++) {
cin >> b[i];
sum += b[i];
}
for (int i = 1; i <= n; i ++) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
// 预处理出状态 i 的硬币钱之和
for (int i = 0; i < (1 << k); i ++) {
int _i = i, t = 0;
while (_i) {
q[i] += (_i % 2) * b[++ t];
_i /= 2;
}
}
for (int i = 0; i < (1 << k); i ++) {
for (int j = 1; j <= k; j ++) {
if (i & (1 << (j - 1))) continue;
// 二分
int l = dp[i] + 1, r = n, mm = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (p[mid] - p[dp[i]] <= b[j]) {
mm = mid;
l = mid + 1;
}
else r = mid - 1;
}
if (mm == -1) continue;
int now = i | (1 << (j - 1));
dp[now] = max (dp[now], mm);
// 如果买完，更新 ans
if (dp[now] >= n) ans = min (ans, q[now]);
}
}
if (ans == 2e9) ans = sum + 1;
cout << sum - ans;
return 0;
}
```
## 总结
状压 DP 的标志是极小的数据范围，同时，进行状压的对象也可以通过数据范围大致确定。再通过前缀和、二分等优化技巧改进状态转移的时间复杂度。