状压DP
蒙德里安的梦想
求把N∗M的棋盘分割成若干个1*2的的长方形，有多少种方案。
先考虑横着放的情况 竖着放的自然唯一确定
状态表示
f[i][j]表示第i 列的每一行小方格被占用的情况j为二进制数 1表示占用
状态计算
用j 表示i列的状态k表示i−1列的状态
能从i−1列转移到i列的条件
① 两列没有冲突的情况 j & k = = 0
②第i−1列所有连续的空白格为偶数j∣k不存在连续奇数个0
const int N = 12, M = 1 << N; LL f[N][M]; bool st[M]; int n, m; int main() { while (cin >> n >> m, n || m) { memset(f, 0, sizeof f); for (int i = 0;i < 1 << n;++i) {//枚举1到n的每一个二进制数 st[i] = true;//假设成立 int cnt = 0;//当前这一段连续0的个数 for (int j = 0; j < n;++j) { if ((i >> j) & 1) {//如果第j位为1 说明上一段连续的0已经结束 if (cnt & 1)st[i] = false; // 如果为奇数 不成立 cnt = 0; // 重置cnt } else cnt++; } if (cnt & 1)st[i] = false; //判断最后一段是否合法 } f[0][0] = 1; for (int i = 1;i <= m;++i) {//枚举每一列 for (int j = 0;j < 1 << n;++j) {//枚举当前列的所有情况 for (int k = 0;k < 1 << n;++k) {//枚举前一列的所有情况 if ((j & k) == 0 && st[j | k])//如果没有冲突并且所有连续的空格为偶数 f[i][j] += f[i - 1][k]; //更新状态 } } } cout << f[m][0] << endl;;//所有第m列没有方格出来的方案数即为答案 } return 0; }
最短Hamilton路径
给定一张 n 个点的带权无向图，点从0 n−1 标号，求起点 0 到终点n−1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
状态表示
const int N = 21, M = 1 << N; int f[M][N]; int mp[N][N]; int main() { int n;cin >> n; for (int i = 0; i < n;++i) { //读入图 for (int j = 0; j < n;++j) { cin >> mp[i][j]; } } memset(f, 0x3f, sizeof f); f[1][0] = 0; // 只经过一个点时 距离为0 for (int i = 0;i < 1 << n;++i) { //状态为i for (int j = 0; j < n;++j) { // 以j为终点 if (i >> j & 1)//经过了j这一点的状态才有意义 for (int k = 0; k < n;++k) //枚举从哪一个点转移过来 if (i - (1 << j) >> k & 1) //没有经过j并且终点为k f[i][j] = min(f[i][j], f[i - (1 << j)][k] + mp[k] [j]); } } cout << f[(1 << n) - 1][n - 1] << endl; //每一个点都经过 且终点为n-1 return 0; }
