状态压缩DP
状态压缩指的是用一个数字的二进制的0/1 来表示所需要的状态
由于复杂度是指数级的 $2^n$
所以一般在$n\le 25$时使用
由于二进制每一位只有$0/1$两种可能性
所以一般可以表示选与不选
另外如果另设一维作为状态转移的途径的话可以转换为状态转移DP
状态压缩通常可以将$O(n!)$复杂度优化为$O(2^n)$
旅行商问题(最短 Hamilton 路径)
TSP全称为Travelling Salesman Problem(旅行商问题),通俗而言,它是指对于给定的一系列城市和每对城市之间的距离,找到访问每一座城市仅一次并回到起始城市的最短回路。
状态压缩有没有经过
$dfs$的时候是$O(n!)$的复杂度,这是因为额外携带了遍历的顺序这个信息
额外信息的存储需要额外的 时间来携带
所以我们可以用二进制来压缩掉经过的顺序
因为距离是只跟目前在的地方有关系,所以就第一维经过的村庄,第二维在的村庄依次遍历就好
code
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#define int long long
int n, m;
const int N = 20;
int f[1 << N][N];
int dist[N][N];
void solve() {
std::cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
std::cin >> dist[i][j];
}
}
std::fill(f[0], f[0] + (1 << N) * N, INT_MAX);
f[1][0] = 0;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((i >> j) & 1) {
for (int k = 0; k < n; k++) {
if ((i >> k) & 1 ^ 1) {
f[i + (1 << k)][k] =
std::min(f[i + (1 << k)][k], f[i][j] + dist[j][k]);
}
}
}
}
}
std::cout << f[(1 << n) - 1][n - 1];
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
std::cout << std::fixed << std::setprecision(15);
std::cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
solve();
return 0;
}
网格(蒙德里安的梦想)
长方形的摆放只与当前位置的最近两行有关
又因为$m\le12$所以我们状态压缩最近一行的方格是横着摆放的还是竖着摆放的
时间复杂度$O(nm2^m)$
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
int n, m;
const int N = 12;
long long f[1 << N], v[1 << N];
void solve() {
while (std::cin >> n >> m, n || m) {
memset(f, 0, sizeof f);
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
memset(v, 0, sizeof v);
for (int k = 0; k < (1 << m); k++) {
if (((k >> (j - 1)) & 1) ^ 1) {
if (i != n) v[k + (1 << (j - 1))] += f[k];
if (j != m and !((k >> j) & 1)) v[k + (1 << (j))] += f[k];
} else {
v[k - (1 << (j - 1))] += f[k];
}
}
memcpy(f, v, sizeof v);
}
}
std::cout << f[0] << "\n";
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
std::cout << std::fixed << std::setprecision(15);
solve();
return 0;
}