Algorithm2.3 状压dp

[TOC]

状压dp

主要特征:n较小 => 暴搜或者状压。【所以主要特征就是可以通过暴力搜索搜出来,但是不能过题,需要用dp,把所有要搜索到的状态压缩到一个01字串中,每个字符都表示】

主要思路:就是将本来某一行的状态是或否的唯二的两种【可能本来需要用数组来储存的】 => 通过用二进制【01来进行储存】

主要原因:用于解决情况之间的耦合性太复杂(就例如八皇后,看上下左右斜上下这些,直接通过压缩成字符串的状态然后来进行位运算即可),如果直接循环遍历去判断的话太麻烦,所以通过状态压缩,

  • 把本来是需要用数组表示的数据结构=>用一个字串直接整体表示
  • 把本来需要循环来计算的=>用位运算来计算

互不侵犯:https://www.luogu.com.cn/problem/P1896

题目大意:类似于八皇后,只不过八皇后是一行一列都会受影响,而这个题只是相邻的上下行受影响。问放n个皇后最多有多少种方式

1、数据结构:

dp[i][j][s]表示在第i行,且第i行的状态为j时,他所需要的国王的个数为s个,此时的种类数量。

2、遍历层次:遍历各个层->遍历某一层所有的可能的状态->遍历所需要的国王的个数->遍历上一行的状态查看是否冲突sit[j]&sit[t] sit[j]>>1&sit[t] sit[j]<<1&sit[t] ,查看这些状态是否冲突

#include <iostream>
using namespace std;
#define maxn 10
#define maxsit (1<<10)+50
#define maxk 105
int n, k, sit[maxk], cnt_sit, num[maxk]; // dp[i][j][s] 表示在第i行,这一行的状态为j(二进制所转换成的十进制之后的数),放了s个目标 的总方案数
typedef long long LL;
LL dp[maxn][maxsit][maxk], ans=0;

// 首先预处理单独这一行,可能的状态,相互之间不冲突,也就是没有相邻的。【注意是线性的,不是环形的,也就是说101这种的是完全可以的】
void init() {
    for (int i = 0; i < (1<<n); ++i) {
        if (i & (i<<1)) continue;
        int sum = 0;
        for (int j = 0; j < n; ++j) if (i & (1<<j)) sum++;
        sit[++cnt_sit] = i;
        num[cnt_sit] = sum;
    }
}

void solve() {
    dp[0][1][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= cnt_sit; ++j)
            for (int l = num[j]; l <= k; ++l)
                for (int t = 1; t <= cnt_sit; ++t)
                    if (!(sit[j]&sit[t]) && !((sit[j]<<1)&sit[t]) && !((sit[j]>>1)&sit[t])) dp[i][j][l] += dp[i-1][t][l-num[j]];
    for (int i = 1; i <= cnt_sit; ++i) ans += dp[n][i][k];
    printf("%lld\n", ans);
}

int main() {
    scanf("%d%d", &n, &k);
    init();
    solve();
    return 0;
}

类似题目:

https://www.luogu.com.cn/problem/P1123

取数游戏,相邻的八个点不可以拿数,取出的所有数的和最大的情况

*DFS和状压dp的界定:*什么时候用DFS,什么时候用状压dp来处理

炮兵阵地:https://www.luogu.com.cn/problem/P2704

题目大意:一个炮车的左一左二,上一上二,右一右二,下一下二都不能放其他的炮车。问总情况数量

吃奶酪:https://www.luogu.com.cn/problem/P1433

题目大意:问放n个奶酪的最短总路径之和

愤怒的小鸟:https://www.luogu.com.cn/problem/P2831

题目大意:

Posted on Feb 1, 2021