「Note」状压dp

近期学习了状压dp,简单做一个小结。

定义

状压dp是动态规划的一种，它通过将多维的状态压缩成一个具有映射关系的数字来实现降维，从而简化代码实现难度。

优点可以通过位运算判断的高效性降低时间，但是当状态的情况无法转换成二进制数的时候会变得比较麻烦。

---

例题

糖果

link
此题并非真正的状压dp，而是一道二进制压缩的板题。
可以用 $|$ 运算求出并集。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
const int MAXM = 1e5 + 5; 

int n, m, sum;
int dp[MAXM], w[MAXN], a[MAXN];

int main() {
	memset(dp, 0x3f, sizeof(dp));
	scanf ("%d %d", &n, &m);
	for (int i = 1, k; i <= n; i++) {
		scanf ("%d %d", &a[i], &k);
		w[i] = 0;
		for (int j = 1, x; j <= k; j++) {
			scanf ("%d", &x);
			w[i] |= (1 << x);
		}
	}
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < (1 << m); j++) {
			dp[j | w[i]] = min(dp[j | w[i]], dp[j] + a[i]);
		}		
	}
	printf ("%d\n", dp[(1 << m) - 1]);
	return 0;
}

最短Hamilton路径

link
暴力枚举状态 $w$, $dp[w][i] = dp[w][i] = min(dp[w][i], dp[w & (~(1 << i))][j] + dis[j][i])$
稍稍处理细节即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 25;
const int MAXM = 1 << 20 + 3;

void read(int& x) {
    x = 0;
    int f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f - f;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    x *= f;
}

void write(int x) {
    if (x < 0) {
        putchar('-');
        x = (~x) + 1;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

int n;
int dis[MAXN][MAXN], dp[MAXM][MAXN];

int main() {
    read(n);
    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++) dp[i][j] = INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0, x; j < n; j++) {
            read(x);
            dis[i][j] = dis[j][i] = x;
        }
    }
    dp[1][0] = 0;
    for (int w = 0; w < (1 << n); w++) {
        for (int i = 0; i < n; i++) {
            if (w & (1 << i) == 0)
                continue;
            for (int j = 0; j < n; j++) {
                if (w & (1 << j) == 0 || i == j)
                    continue;
                dp[w][i] = min(dp[w][i], dp[w & (~(1 << i))][j] + dis[j][i]);
            }
        }
    }
    printf("%d\n", dp[(1 << n) - 1][n - 1]);
    return 0;
}

Mondriaan’s Dream

link
开始有点难度了。
按格dp，对上方和左方的格子的占用情况进行讨论转移。0表示已放置，1表示未放置。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXM = 1 << 11;
const int MAXN = 15;

void read(int& x) {
	x = 0;
	int f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') f - f;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	x *= f;
}

void write(int x) {
	if (x < 0) {
		putchar('-');
		x = (~x) + 1;
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

int n, m;
bool in_s[MAXM];
long long dp[MAXN][MAXM];

int main() {
	while (scanf ("%d %d", &n, &m), n, m) {
		for (int i = 0; i < (1 << m); i++) {
			bool cnt = 0, has_odd = 0;
			for (int j = 0; j < m; j++) {
				if (i & (1 << j)) has_odd |= cnt, cnt = 0;
				else cnt ^= 1;
			}
			in_s[i] = cnt | has_odd ? 0 : 1;
		}
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < (1 << m); j++) {
				dp[i][j] = 0;
				for (int k = 0; k < (1 << m); k++) {
					if (in_s[j | k] && (j & k) == 0) {
						dp[i][j] += dp[i - 1][k];
					}
				}
			}
		}
		printf ("%lld\n", dp[n][0]);
	}
	return 0;
}

working…