分析

基于连通性的转态压缩$dp$也是用二进制来实现”压缩”，但压缩的通常是一条”路线”，或者说是选点的方案。

例题分析

① 最短哈密顿路径

本题就是用二进制来”压缩”路线，$1$表示路线上有该点，$0$则没有。然后剩余的就是在不同状态之间转移了

② 愤怒的小鸟

本题二进制”压缩”的是抛物线，$1$表示该小鸟在抛物线上，$0$则不在。先预处理出所有抛物线，再判断每只小鸟是否在该抛物线上，如果在该抛物线上，就加上小鸟的序号$k$的$1$<<$k$，这样就能表示出每只小鸟是否在某条抛物线上了。

③ 得到新鲜甜甜圈的最多组数

$40$位二进制，最低五位表示的是余数为$1$的组有多少个，最高五位表示的是余数为$8$的组数有多少个

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
// 冗余：a0,a1,...,an中存在大量重复搜索，比如1,1,3,3,5,5
// 前两层递归搜索1,3其实只需要进行一次，因此需要记忆化搜索
// 而要将a0,a1,...,an的排列状况记忆下来，即需要(8×5=40)位2进制
// 8表示从除0之外余数的可能值([1,8])，5表示每个余数都可能有30个(5为二进制表示个数)
// 直观理解为，最低五位表示的是余数为1的组有多少个，最高五位表示的是余数为8的组数有多少个
class Solution {
public:
    int maxHappyGroups(int k, vector<int>& g) {
        int n = g.size(), ans = 0;
        unordered_map<LL, int> f;
        LL state = 0;
        for (auto t : g)
        {
            int i = t % k;  // 判断是否为k的整数倍
            ans += i == 0;  // 如果为0直接将所有的安排到最前面优先处理
            if (i) state += 1LL << (i * 5);  // 如果不为1则加到总方案上面
        }

        function<int(LL, int)> dfs = [&](LL state, int resid)
        {
            if (f.count(state)) return f[state];  // 记忆化搜索
            int res = 0;
            int x = resid == 0;  // 如果前面的剩余客人数为0，那么快乐的客人组数+1
            for (int i = 1; i < k; i ++)  // g中客人的可能数值mod k后为[0,k)
                if (state >> (i * 5) & 31)  // 余数为i的组还有值
                {
                    int t = dfs(state - (1LL << (i * 5)), (resid + i) % k);  // 将余数为i的所有组安排一个之后继续递归
                    res = max(res, t + x);
                }
            return f[state] = res;
        };
        return ans + dfs(state, 0);
    }
};