状压DP
状压dp一定要注意位运算的优先级问题(从上到下优先级降低)
(),[ ]
/,*,\%
+ ,-
<<,>>
>,>=,<,<=
==,!=
\&
\hat{}
|
\&\&
||
+=,-=,\&=,\hat{}=,|=,
摸鱼
蜗蜗一共有 n 天假期，在假期的第 i 天摸鱼他会得到 a[i] 的快乐值。如果蜗蜗每天都摸鱼的话，他会有愧疚感，所以蜗蜗制定了这么个计划：对于每一天，蜗蜗都有一个列表，如果蜗蜗在列表中的每一天都在摸鱼的话，这一天蜗蜗就不能摸鱼。现在请问蜗蜗如何摸鱼，使得他能获得的快乐值总和最大？请求出快乐值总和最大是多少。
每一组方案可以用一个长度为n的二进制字符串来表示（1表示摸鱼，0表示不摸鱼），例如当n=5时，10111表示在第1,3,4,5天摸鱼。
有n个数位的二进制字符串可以和十进制[1,2^n]转换，所以枚举十进制数字就可以知道具体在哪一天摸鱼了
遍历每一种摸鱼的情况，把每一天的摸鱼情况用数组b[i]表示，b[i]表示在第i天是否摸鱼
因为蜗蜗有一个列表，如果蜗蜗在列表中的每一天都在摸鱼的话，这一天蜗蜗就不能摸鱼，所以还要判断蜗蜗在数组b的摸鱼状态下，在第i天是否还能摸鱼，
用数组s记录列表中的每种状态，用十进制来表示二进制下每天摸不摸鱼；对于第i天，如果s[i]&i==s[i]；那么根据题意，这一天就不能摸鱼。
int n, a[21], l[21], s[21], b[21];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
scanf("%d", &l[i]);
for (int j = 1; j <= l[i]; j++) {
int x; cin >> x;
s[i] |= 1 << (x - 1);//记录s[i]
}
}
int ans = 0;
for (int i = 1; i <= 1 << n; i++) {//枚举每一种摸鱼的情况
for (int j = 1, k = i; j <= n; j++, k /= 2) {//计算b[i]
if (k & 1) b[j] = 1;
else b[j] = 0;
}
bool ok = true;
for (int j = 1; j <= n; j++) {//判断这一天能不能摸鱼
if (b[j] && l[j] && (i & s[j]) == s[j]) {
ok = false;
}
}
if (!ok) continue;
int res = 0;
for (int j = 1; j <= n; j++) {
if (b[j]) res += a[j];
}
ans = max(ans, res);
}
printf("%d", ans);
return 0;
}旅行商
蜗蜗的世界里有 n 个城市，城市两两之间通过高速公路连接，从第 i 个城市走到第 j 个城市需要花费
a[i][j]的时间。现在蜗蜗想从 1 号城市出发旅游，他想把每个城市都玩个遍，但又不想在一个城市玩两遍，玩完以后蜗蜗需要回到 1 号城市应付期末考试。请问蜗蜗最少需要花费多少时间？
蜗蜗到了一个城市以后，一定会在这个城市游玩。蜗蜗在出发之前会先在 1 号城市游玩。连接两个城市的高速公路不会经过其他城市。由于路况的原因，从第 i 个城市走到第 j 个城市花费的时间不一定等于从第 j 个城市走到第 i 个城市花费的时间。
在之前的旅途中，去过的城市的顺序是不重要的，于是我们可以用f[i][j]表示去过的城市的状态是i（i记录哪些城市去过，哪些城市没去过），现在在j号城市花费的最短时间。
用长度为n的二进制字符串记录，从左往右第x个位置表示蜗蜗有没有去过x号城市，1表示去过，0表示没去过，就可以用十进制数字表示去过的城市状态了。
最后答案等于min_{2\leq j\leq n}(f[2^n-1][j]+a[j][1])
具体实现为：枚举每种状态，依次遍历每个位置j，如果f[i][j] < 1 << 30,说明j城市没有去过，然后考虑从j到k转移
int n, a[19][19], f[1 << 18][19];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
memset(f, 127, sizeof(f));
f[1][1] = 0;
for (int i = 1; i < (1 << n); i++) {
for (int j = 1; j <= n; j++) {
if (f[i][j] < 1 << 30) {
for (int k = 1; k <= n; k++) {
if (!(i & (1 << (k - 1))))
f[i + (1 << (k - 1))][k] = min(f[i + (1 << (k - 1))][k], f[i][j] + a[j][k]);
}
}
}
}
int ans = INF;
for (int i = 2; i <= n; i++) {
ans = min(ans, f[(1 << n) - 1][i] + a[i][1]);
}
printf("%d", ans);
return 0;
}消除
桌面上有 n 个方块，蜗蜗想把它们都消除掉。每个方块有个权值，第 i 个方块的权值等于 a[i]。每一次消除蜗蜗有两种选择：
1.选择一个还没有被消除的方块 i，付出 a[i] 的代价把它消除；
2.选择两个还没有被消除的方块
i,j(i≠j)，付出a[i] xor a[j]的代价把它们消除；请问蜗蜗最少需要花费多少代价，能把 n 个方块都消除掉？
用一个长度为n的二进制字符串记录，从右往左第x个位置表示第x个方块有没有被消除（1表示被消除，0表示没有被消除）
int n, a[21], f[1 << 20];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
memset(f, 127, sizeof(f));
f[0] = 0;
for (int i = 0; i < (1 << n); i++) {//枚举每一种情况
for (int j = 1; j <= n; j++) {//当前删除j
if (!(i & (1 << (j - 1)))) {//判断j是否已经被删除
f[i + (1 << (j - 1))] = min(f[i + (1 << (j - 1))], f[i] + a[j]);//删除j
for (int k = j + 1; k <= n; k++) {//删除j和k
if (!(i & (1 << (k - 1))))//判断k是否被删除
f[i + (1 << (j - 1)) + (1 << (k - 1))] = min(f[i + (1 << (j - 1)) + (1 << (k - 1))], f[i] + (a[j] ^ a[k]));
}
}
}
}
printf("%d", f[(1 << n) - 1]);
return 0;
}实际上，对于一个状态i，我们优先消除编号最小的没有被消除的方块就可以了；其他的情况在别的状态下会考虑到
非常巧妙
int n, a[21], f[1 << 20];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
memset(f, 127, sizeof(f));
f[0] = 0;
for (int i = 0; i < (1 << n); i++) {
for (int j = 1; j <= n; j++) {
if (!(i & (1 << (j - 1)))) {
f[i + (1 << (j - 1))] = min(f[i + (1 << (j - 1))], f[i] + a[j]);
for (int k = j + 1; k <= n; k++) {
if (!(i & (1 << (k - 1))))
f[i + (1 << (j - 1)) + (1 << (k - 1))] = min(f[i + (1 << (j - 1)) + (1 << (k - 1))], f[i] + (a[j] ^ a[k]));
}
break;//与上一个代码的区别只是多加了一个break;找到编号最小的没有被消除的方块处理后就跳出
}
}
}
printf("%d", f[(1 << n) - 1]);
return 0;
}麦当劳
喜欢吃麦当劳的蜗蜗要在学校呆 n 天，如果第 i 天蜗蜗吃到了麦当劳，他可以获得 a[i] 点快乐值。然而蜗蜗不能吃太多麦当劳，在连续的 m 天中，他最多只能有一半的天数吃麦当劳。请问蜗蜗在这 n 天中最多可以得到多少快乐值？
由于n太大了，所以直接枚举n肯定不行，由于m很小，所以我们用f[1<<m]进行状态转移，对于第i天，我们只需要从第i天开始往左数m天每天吃不吃麦当劳就可以了
用f[i][j]表示考虑到第i天，最近m天每天吃不吃麦当劳的状态为j（j记录了这m天中哪些天吃了麦当劳，哪些天没吃）的情况下最大快乐值是多少
j可以用二进制字符串表示
当i变成i+1时，j/2即可，在根据第i+1天吃不吃麦当劳，考虑是否加上(1 << (m - 1))
int n, m, f[256], v[256], a[100001];
bool b[256];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
memset(b, false, sizeof(b));
for (int i = 0; i < 1 << m; i++) {
int cnt = 0;
for (int j = 0; j < m; j++)
if (i & (1 << j)) cnt++;
if (cnt <= m / 2) b[i] = true;
}
memset(f, 128, sizeof(f));
f[0] = 0;
for (int i= 1; i <= n; i++) {
memset(v, 128, sizeof(v));
for (int j = 0; j < 1 << m; j++) {
if (f[j] >= 0) {
v[j / 2] = max(v[j / 2], f[j]);//第i天不吃麦当劳
if (b[j / 2 + (1 << (m - 1))])//第i天吃麦当劳
v[j / 2 + (1 << (m - 1))] = max(v[j / 2 + (1 << (m - 1))], f[j] + a[i]);
}
}
memcpy(f, v, sizeof(f));
}
int ans = 0;
for (int i = 0; i < 1 << m; i++) {
ans = max(ans, f[i]);
}
printf("%d\n", ans);
}
Last updated