用记搜暴打所有 DP 题?!（2）（状压 DP ）

· · 算法·理论

书接上回

这是我最要重点讲的一部分，此内容下共有 12 道状压经典例题，都在这个题单里了。

前置部分（关于位运算）：

操作 位运算（‘或’在表格内表示不出来用中文代替）
取出整数 n 二进制下的第 k 位（从右往左数） (n>>k)&1
对整数 n 二进制表示下的第 k 位赋值 1 n或(1<<k)
对整数 n 二进制表示下的第 k 位赋值 0 n&(!(1<<k))
对整数 n 二进制表示下的第 k 位取反 n^(1<<k)

当然还有许多位运算技巧，这些技巧需根据题目来确定是否使用。

进入正题，状压 dp 类型的题目也是有三部曲的：

写出爆搜->将题目类型中无法代替掉的标记数组用一个变量来表示->记忆化。

我们可以通过以下题目来理解。

1.求最短/长路径型状压

1.1 P10447 最短 Hamilton 路径

看到题目就会想到用 Dfs 枚举全排列然后统计的做法吧，但实际上这是 O(n\times n!) 的时间复杂度，显然无法通过此题。

但是我们可以思考另一种思路，在每到过一个地方就用标记数组进行标记（保证以后走不到），然后求当前最短路写出。

但是会发现一个问题，就是一个状态会重复多次计算导致复杂度又变成了 O(n!) 的时间复杂度，而这个标记数组有去不掉，怎么办好呢？

这时候就需要用状压来代替标记数组了，每到过一个点上时我们就在这个点上的二进制数位上设为 1 ，表示这个点已经走过，这样就可以记忆化从而不用重复计算一个状态了（这里还需要注意的一点是不到最后一步是不可以走到点 n-1 的，需要特判）：

int dfs(int u, int vis, int y) {
    if (y == n) return 0;
    if (dp[u][vis] != INT_MAX) return dp[u][vis];
    for (int i = 0; i < n; ++i) {
        if (vis >> i & 1 || u == i || (y < n - 1 && i == n - 1)) continue ;
        dp[u][vis] = min(dp[u][vis], dfs(i, vis | (1 << i), y + 1) + w[u][i]);
    }
    return dp[u][vis];
}

那么时间复杂度就是 n 位二进制数的数量，也就是 O(2^n) ，而这道题的数据范围是 n \le 20 ，显然可以通过这道题。

使用记搜写这道题就相较于直接 dp 代码量少很多，这里就可以体现出记搜的魅力了。

相似例题

P1171 售货员的难题，\ P4802 [CCO 2015] 路短最。

1.2 P4772 灰化肥，会挥发

看上去似乎是一道 bfs 模题，但实际上还真需要 bfs 。

可以先用对每个点 bfs 建一个邻接矩阵记录每个点到其他点的距离：

bool check(int xx, int yy) {
    return xx > r || yy > c || xx < 1 || yy < 1;
}
void bfs(int uid, int sx, int sy) {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0, sizeof(dis));
    q.push({sx, sy});
    vis[sx][sy] = 1;
    while (!q.empty()) {
        Node u = q.front();
        q.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = u.ux + fx[d];
            int ny = u.uy + fy[d];
            if (check(nx, ny) || ma[nx][ny] == '*' || vis[nx][ny]) continue ;
            dis[nx][ny] = dis[u.ux][u.uy] + 1;
            vis[nx][ny] = 1;
            q.push({nx, ny});
            if (ma[nx][ny] != '*' && ma[nx][ny] != '.') 
                w[uid][ma[nx][ny] - 'A' + 1] = dis[nx][ny];
        }
    }
}

然后这题就变成了类最优哈密顿路径的题（只不过这题不需要最后一步到达最后一个点）。

但是本题的难点就在于如何输出方案。

我们可以维护一个结构体 dp 与结构体的 dfs ，用来记录方案与此时的距离。（取最小值时注意判断最小字典序就行），大体的部分是和 1.1 一样的：

pair <int, string> dfs(int u, int vi, int z) {
    // printf("\n%d %d %d\n", u, vi, z);
    char ct = u - 1 + 'A';
    string s = "";
    s += ct;
    if (z == n) return {0, s};
    if (dp[u][vi].val != INT_MAX) {
        // cout << dp[u][vi].val << " " << dp[u][vi].t << "\n";
        return {dp[u][vi].val, dp[u][vi].t};
    }
    for (int i = 2; i <= n; ++i) {
        if ((vi >> i) & 1) continue ;
        pair <int, string> ans = dfs(i, vi | (1 << i), z + 1);
        ans.second.insert(0, 1, ct);
        ans.first += w[u][i];
        if (ans.first < dp[u][vi].val) 
            dp[u][vi] = {ans.first, ans.second};
        else if (ans.first == dp[u][vi].val && ans.second < dp[u][vi].t)
            dp[u][vi] = {ans.first, ans.second};
    }
    // cout << dp[u][vi].val << " " << dp[u][vi].t << "\n";
    return {dp[u][vi].val, dp[u][vi].t};
}

还是要注意此处的代码细节，作者为了调这道题耗时 2h 。

相似例题

P1433 吃奶酪。

2.摆放类型状压

2.1 八皇后

一个如下的 6 \times 6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 2\ 4\ 6\ 1\ 3\ 5 来描述，第 i 个数字表示在第 i 行的相应位置有一个棋子，如下：

行号 1\ 2\ 3\ 4\ 5\ 6

列号 2\ 4\ 6\ 1\ 3\ 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。

非常经典的状压题目，但是单论这道题而言，是可以直接用搜索做的，作者把这个放上来只是为了解释什么叫摆放类型 dp 。

2.2 P1879 [USACO06NOV] Corn Fields G

这一题的状态似乎不太一样，因为上一行的状态可以关系到下一行。

我们可以一次性枚举一行的所有情况，检查是否让所有奶牛都在草地上且他的左右与上方没有其他奶牛。时间复杂度为 O(2^n \times 2^m) = O(2^{n+m}) ，可以通过此题。

思路是好想的但是位运算是残酷的，那请问如何用位运算实现检查是否让所有奶牛都在草地上且他的左右与上方没有其他奶牛呢？

不妨先设目前奶牛的状态为 i ，这一行草地的状态为 a ，上一行奶牛的状态为 pre 。

则判断当前这一行奶牛是否相邻的语句为 i&(i<<1) 。

其实这挺好理解的，就是让当前状态的奶牛都向左移动一位检查是否与原来状态的奶牛重合，若没有重合，则 (i<<1) 里有 1 的位上 i 的同一位必为 0 ，则根据按位与的性质，有 0 则 0 ，则原语句为 0 。反之，若重合，则原语句大于 0 。

其实不需要判断每个奶牛都在草地上了，我们的当前正确决策可以直接变为 i&a ,也是根据按位与的性质易证。但是当前的正确决策容易重复，故在函数内可以搞一个标记数组检查当前决策是否被使用过。

判断上前这一行的奶牛是否与上一行相邻就更简单了，就是检查上一行是否与这一行有同为 1 的位置就可以了，若有，则 i&pre 大于 0 ，若没有，则 i&pre 为 0 。

好的作者终于把这道题所需要的位运算给讲完了，结合之前的思路，我们可以写出如下代码：

int dfs(int u, int pre) {
    if (dp[u][pre]) return dp[u][pre];
    if (u == n + 1) return 1;
    bool vis[1 << N] = {0};
    for (int i = 0; i < (1 << m); ++i) {
        if (i & (i << 1) || i & pre) continue ;
        int t = i & a[u];
        if (vis[t]) continue ;
        dp[u][pre] += dfs(u + 1, t), dp[u][pre] %= Mod;
        vis[t] = 1;
    }
    return dp[u][pre];
}

小技巧：这道题的 a 数组可以这样去储存：

for (int i = 1; i <= n; ++i)
        for (int j = 1, t; j <= m; ++j) {
            scanf("%d", &t);
            a[i] <<= 1, a[i] |= t;
        }

从这道题可以告诉我们不必要拘于原有的位运算，可以自己去发现位运算的性质去灵活运用。

2.3 p5005 中国象棋-摆上马

这题是上题的进化版，考虑的情况超级多，作者被困 1h 才调出来，还要考虑马脚！！！！！

细节还是很多的，重点可以放在下面的 check 函数上。

#include <bits/stdc++.h>
using namespace std;
const int N = 7, Mod = 1e9 + 7;
int n, m, dp[100][1 << N][1 << N];
bool check(int now, int pre1, int pre2) {
    for (int i = 0; i < m; ++i) {
        if ((now >> i) & 1) {
            if ((pre1 >> (i - 2)) & 1 && !((pre1 >> (i - 1)) & 1)) return 0;
            if ((pre1 >> (i + 2)) & 1 && !((pre1 >> (i + 1)) & 1)) return 0;
            if ((pre2 >> (i - 1)) & 1 && !((pre1 >> (i - 1)) & 1)) return 0;
            if ((pre2 >> (i + 1)) & 1 && !((pre1 >> (i + 1)) & 1)) return 0;
            if ((pre1 >> (i - 2)) & 1 && !((now >> (i - 1)) & 1)) return 0;
            if ((pre1 >> (i + 2)) & 1 && !((now >> (i + 1)) & 1)) return 0;
            if ((pre2 >> (i - 1)) & 1 && !((pre1 >> i) & 1)) return 0;
            if ((pre2 >> (i + 1)) & 1 && !((pre1 >> i) & 1)) return 0;
        }
    }
    return 1;
}
void putc(int x) {
    for (int i = 0; i < m; ++i)
        cout << ((x >> i) & 1) << " ";
}
inline int dfs(int u, int pre1, int pre2) {
    // printf("%d %d %d %d\n", u, pre1, pre2, y);
    if (u == n) return 1;
    if (dp[u][pre1][pre2]) return dp[u][pre1][pre2];
    for (int i = 0; i < (1 << m); ++i) {
        if (!check(i, pre1, pre2)) continue ;
        dp[u][pre1][pre2] += dfs(u + 1, i, pre1);
        dp[u][pre1][pre2] %= Mod;
    }
    return dp[u][pre1][pre2];
}
int main() {
    scanf("%d%d", &n, &m);
    printf("%d", dfs(0, 0, 0));
    return 0;
}

但是还没完！作者都快被搞崩溃了！

原来这道题 1MB 的极限空间导致作者直接 MLE 。

作者非常生气地打开题解发现要用滚动数组优化，但是记搜没法使用这个啊，怎么办！

于是作者使用人类智慧——打表成功解决这道题：

#include <bits/stdc++.h>
using namespace std;
const int c[] = {0,2,4,8,16,32,64,4,16,43,104,281,801,8,43,145,425,1519,5760,16,104,425,1823,9312,47768,32,281,1519,9312,71937,523062,64,801,5760,47768,523062,5405377,128,2217,20965,235763,3647362,52099173,256,6002,73098,1162092,25620824,509729748,512,16346,259225,5797340,184056479,111556574,1024,44891,930403,29000006,311261872,87976699,2048,123206,3343682,144757129,335020825,273085875,4096,337177,11925514,722209668,350274632,224770477,8192,922513,42558245,605814004,250120743,640524640,16384,2526285,152056330,8923952,789763322,93036993,32768,6919800,543944948,936931325,662748501,271270542,65536,18949168,943851635,124894604,253114435,25883187,131072,51884131,946163503,921030358,28842761,254864339,262144,142071988,820507947,455965417,355726142,942277521,524288,389049157,716280187,679402150,828664453,976105583,1048576,65354898,61310726,981008445,574874573,881972978,2097152,917264467,143120177,91014688,789813839,621062045,4194304,988366717,541007178,951630215,838848475,204848836,8388608,874748211,720206790,909178202,472666730,561166340,16777216,900213286,416854348,220957573,97637352,758648341,33554432,26024554,525627034,169136251,438688642,278699013,67108864,155707102,154225664,105001795,391910627,110222845,134217728,932711218,72383817,108705749,418827891,439362081,268435456,952056860,755945548,129534197,934362426,378415500,536870912,536443366,362163904,949484162,195976763,881742231,73741817,269391258,447260590,506053876,341645872,798932039,147483634,309986185,963956172,465373741,928198042,773000309,294967268,745344970,592799511,452041846,621423099,444071487,589934536,59534992,294634251,659595427,44480224,894682348,179869065,620607889,856239677,82022677,899406419,923916098,359738130,993055680,69601873,415616035,99376989,975930159,719476260,229845220,220318651,648244619,306771950,305524671,438952513,401359595,457946927,201368083,582717709,299194896,877905026,612742058,172143861,98276734,807293944,673345944,755810045,795013047,424652224,201006259,725030616,378257655,511620083,462856978,199568644,4529396,857005674,358758720,23240159,883971048,319137217,853283235,272205817,547482724,46480318,464513310,332513459,932626029,413531798,510826934,92960636,313689830,930164472,636081232,301083839,249825004,185921272,907079491,411534200,507716057,784440631,878429118,371842544,861101919,955299562,568461197,142062220,305447538,743685088,875872311,3127405,795066256,971812293,313905509,487370169,442417891,35000174,143673838,695062874,433457720,974740338,511453848,211464848,330052628,828441767,305363891,949480669,338003935,855895623,708104183,501027405,986610659,898961331,933997067,621190474,92652918,233824137,25116436,797922655,591476837,362030096,38934368,142084107,502830718,595845303,684139316,101486197,442382699,606585253,670177905,191690599,627494454,328176682,85326885,856362128,457687686,383381198,462238341,774388684,841327267,910876672,794740357,766762396,932057225,599827225,998231110,507491883,352022570,533524785,139883396,467470732,397977392,957878446,16630334,67049563,572962198,319838714,894489734,567732749,788469739,134099126,266860169,649461005,927688357,422207876,569545194,268198252,146621798,711111525,892589458,92790639,970358000,536396504,205506896,634672993,270306351,486566500,269496787,72793001,780234347,716597,916610802,962439586,256102952,145586002,579571950,933882557,776178595,150337247,839562430,291172004,61207442,956679547,903797621,267079462,506548813,582344008,506897756,61576196,197949933,476935741,449016010,164688009,585024824,375850302,157608358,159679355,498943171,329376018,945262337,874734031,549924309,490327420,319318929,658752036,613125679,725252819,236996291,944435656,428483228,317504065,625557350,83267204,940916708,265688378,682179340,635008130,601298123,939614975,436373618,122182123,318443828,270016253,142363835,431866181,860392909,322349445,700797283,540032506,127021559,116970576,660118195,522768992,773721326,80065005,887919712,663191714,381118343,491313295,120332041,160130010,649278885,833869257,871951506,738214415,560848207,320260020,638056495,921309189,601013114,943503253,357214451,640520040,129379701,283779038,366201849,738186512,563095277,281040073,422320736,914643750,723260029,126121595,292482157,562080146,810904889,573802698,563804887,679357707,61920227,124160285,969005853,45608836,373306792,91306663,81101871,248320570,293513189,980303085,472250788,649396812,631434637,496641140,374077781,393466015,387437967,400194160,701569221,993282280,763780540,717992482,614764063,587894098,101136055,986564553,167357495,682894780,574989221,698172336,693654296,973129099,24047768,468203628,132328374,509045756,713896588,946258191,856984379,946641902,638594540,538458434,381291906,892516375,955045979,136624738,458314221,987204172,20917462,785032743,187825908,10245809,564810838,811972205,117519448,570065479,25043399,657049176,653019833,46361369,457927520,140130951,346194706,600344842,896987635,334245322,436845950,280261902,158109382,123293247,758347019,737998515,68065036,560523804,307143608,236670374,927269164,132782392,96463421,121047601,751876410,265173963,160426792,933547009,387998353,242095202,786710852,754480302,470062829,817490238,499103324,484190404,257949655,264874361,732987407,68839985,958272107,968380808,697390513,587432352,997596235,675045258,275151706,936761609,626720603,748241463,2185515,184821140,363731865,873523211,973383886,59010431,139125983,342547191,311112797,747046415,814786290,221157839,118722594,12599722,759342863,494092823,259484466,821347937,84429634,857768645,638934504,988185646,617722852,595207171,664631965,680628322,883086670,976371285,819598874,994785882,734873229,596791500,394859479};
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    printf("%d", c[6*(n-1)+m]);
    return 0;
}

这道题目告诉我们当空间不够就用打表来凑（滑稽）。

2.4 本小结习题

P1879 [USACO06NOV] Corn Fields G，\ P2704 [NOI2001] 炮兵阵地。

3.其他类型状压

1.字符串接龙状压

3.1 P1278 单词游戏

就是判断下一个单词的开头是不是和当前单词的末尾相同，然后搜下去状压记忆化就行。

int dfs(int vis, int u) {
    if (dp[u][vis]) return dp[u][vis];
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if ((vis >> i) & 1 || (a[u].back() != a[i].front() && u != 0)) continue ;
        cnt = max(dfs(vis | (1 << i), i), cnt);
    }
    return dp[u][vis] = cnt + a[u].size();
}

2.序列安排类状压

3.2 P2915 [USACO08NOV] Mixed Up Cows

直接依照题目写出爆搜然后状压记忆化即可（真心觉得这道题没有蓝）。

long long dfs(int step, int vis, int pre) {
    // printf("%d %d %d\n", step, vis, dp[step][vis]);
    if (step == n) return 1;
    if (dp[pre][vis] != 0) return dp[pre][vis];
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        if ((vis >> i) & 1) continue ;
        if (step && abs(a[pre] - a[i]) <= k) continue ;
        ans += dfs(step + 1, vis | (1 << i), i);
    }
    // printf("\n%d\n\n", ans);
    return dp[pre][vis] = ans;
}

4.结语

希望大家在阅读完本篇文章之后可以对记忆化搜索有更深刻的体会。

本篇文章完结撒花~★,°:.☆(￣▽￣)/$:.°★ 。