前言
重新来吧 别输在过去最得意的事上。
只是单纯的记录一下这个小知识点。
很多时候，题目可以转化为求最大带权最小点覆盖或者是最大独立集。
但是他又经常把这个范围给到 \(n\le 40\) 这种看上去可以用指数又不太能用指数的情况。
可能这个时候你就需要用到短小精悍的它。
基于状压和折半的独立集算法
首先给出我开始弄明白这个小知识点的来源题目：CF1767E Algebra Flash
题意是比较清楚的。
而你要从起点到达终点的一个充分必要条件是：
-
必须选择起点和终点。
-
相邻两个点必须选择一个点。
故你考虑对于起点和终点的颜色连一个自环，然后将相邻两个点分别对应的颜色连一条边。
故这个题就转化成了一个一般图最小带权点覆盖的问题。
而我们知道最小带权点覆盖 \(=\) 点权和 \(-\) 最大带权独立集。（注意这个东西在一般图上也是存在的）
故我们只需要知道这个图的最大带权独立集是什么。
首先有一个很 \(\texttt{naive}\) 的状压是定义 \(dp_S\) 表示只选择 \(S\) 内部的点可以构成的最大独立集是多少。
另外，我们定义点 \(x\) 的邻域的点构成的集合是 \(N(x)\)。
转移的话本质上我们只需要考虑这个集合中的任意一个点就行了，为了方便我们后面的优化，考虑 \(\text{highbit}(S)\)，假设是 \(u\)。
显然有：\(dp_S=\max(dp_{S-u},dp_{S-N(u)-u}+w_u(u\not \in N(u)))\)。（显然如果是自环的话你不能把这个点当作最大独立集上的点）
时间复杂度 \(\mathcal{O}(2^n)\)。
但是这里 \(n\le 40\) 显然不可过啊。
于是我们考虑一个奇技淫巧，也是这个算法的关键所在。
首先先把这个 \(\text{dp}\) 搬到记忆化搜索上面。由于我们使用的是 \(\text{highbit}(S)\)，故这个 \(S\) 在搜素过程中逐渐减小。故我们考虑只对 \(s < 2^{\frac{n}{2}}\) 这部分进行记忆化，而剩下的部分直接爆搜，具体见下：
long long dfs(long long sta)
{
if(sta <= lim && ~dp[sta]) return dp[sta];
if(sta == 0) return 0;
int x = __lg(sta);
long long ans = dfs(sta - (1ll << x));
if(!((1ll << x) & d[x + 1])) ans = max(ans, dfs(sta - (1ll << x) - (sta & d[x + 1])) + w[x + 1]);
if(sta <= lim) return dp[sta] = ans;
return ans;
}
时间复杂度我们简单的证明一下。
对于搜索的前 \(\frac{n}{2}\) 层，每向下递归一次，最多只会变成两个，故前半是 \(\mathcal{O}(2^{\frac{n}{2}})\)。
对于后面的 \(\frac{n}{2}\) 层，显然都会被记忆化到，无论你前面有多少种状态，加起来仍然只有 \(2^{\frac{n}{2}}\) 级别。（就是在记忆化和非记忆化分层的哪些点只有 \(2^{\frac{n}{2}}\) 而他们分别向外扩展也只会扩展成 \(2^{\frac{n}{2}}\) 级别，有点像 \(\text{Meet in the middle}\) 那种感觉）
故总时间复杂度 \(\mathcal{O}(2^{\frac{n}{2}})\)。
本题代码和更多细节见此。
后记
还有一个叫做 \(\text{Bron-Kerbosch}\) 的算法，笔者认为在 \(\texttt{OI}\) 中的实用性远不如文章中这一种，故略过。
缝缝补补，缺漏的知识点会补的完吗？
标签：frac,text,独立,long,算法,带权,快速,dp From： https://www.cnblogs.com/SFsaltyfish/p/18432219