状态压缩dp

标签：状态 le int text 压缩 枚举 mathcal 复杂度 dp

相关技巧

• 枚举子集：如果一个集合状态 \(S\) 由其所有子集 \(S0\subsetneq S\) 转移得到，这样转移的时间复杂度为 \(\sum\limits_{i = 0} ^ n\dbinom n i 2 ^ i=3 ^ n\)

for(int S0 = S; S0; S0 = (S0 - 1) & S) {
{
	...
}

• 高维前缀和

考虑二维前缀和还可以怎么计算：对于每一维，枚举剩下所有维的所有可能，计算关于该维的前缀和。

高维前缀和就是这样的原理。通常情况下每个维度大小为 \(2\)，维数为 \(n\)：枚举每一维 \(d\)，然后枚举所有状态（用二进制数来表示），如果当前状态 \(i\) 的第 \(d\) 位为 \(1\)，就加上 \(i-2^d\) 那个状态的值。

for(int d=0;d<n;d++)
    for(int i=0;i<1<<n;i++)
        if((i>>d)&1)f[i]+=f[i^(1<<d)];

时间复杂度 \(\mathcal O(n2^n)\)

HDU 4628 Pieces （子序列状压的一般套路）

题目

给定一个长度为 \(n\) 的字符串,一次操作定义为选出一个回文子序列并删掉,问将整个字符串删完的最少的操作次数

\(n\le 16\)

题解

设 \(f[s]\) 表示将序列 \(s\) 完全删除的最小的操作次数,对于所有 \(s\) 为回文串的 \(f[s]=1\) ,转移就是枚举子集转移 \(f[s]=\min_{x\subseteq s} f[x]+f[s^x]\),其中 \(x\) 是回文串,时间复杂度 \(\mathcal O(3^n)\)

HDU 6149 Valley Number II （图上状压一般思路）

题目

给定一个 \(n\) 个点 \(m\) 条边的无向图,其中 \(k\) 个点被标记为高点,\(n-k\) 个点被标记为低点

一个山谷定义为一个三元组 \(<x,y,z>\) ,满足 \(x,z\) 是高点, \(y\) 是低点,而且 \(x,y\) 和 \(y,z\) 之间均有边相连

如果一个点只能在一个山谷中,求这张图最多有多少个山谷

\(x\le 30,k\le \min(n,15)\)

题解

首先,注意到 \(k\) 的范围是很小的,所以我们考虑将高点的使用情况进行状压

设 \(f[i][s]\) 表示考虑到第 \(i\) 个低点,使用了集合 \(s\) 中的高点,所能够形成的山谷有多少个

假设我们考虑到第 \(i\) 个点,要向 \(i+1\) 进行转移,那么就在图中找到所有与 \(i+1\) 相连的高点,然后转移即可

P3959 [NOIP2017 提高组] 宝藏 （分层法确定DP顺序）

题目

给定一个 \(n\) 个点 \(m\) 条边的无向图,边有边权。找到这张图的一棵生成树,记一个点到根距离为 \(\text{L}\) ,点的个数为 \(\text{K}\) ,这个点的贡献为 \(\text{L}\times \text{K}\) ,要求最小化贡献和

题解

考虑根据离根的深度(从当前到根经过的点数),一层一层进行DP

设 \(f[i][s]\) 表示考虑到第 \(i\) 层,选了 \(s\) 集合中的点的最小贡献

转移为

\[f[i][s]=\min\lbrace f[i-1][s_0]+\text{cost}(s_0,s)\times (i+1) \rbrace \]

其中 \(\text{cost}(s_0,s)\) 表示的是从状态 \(s_0\) 到 \(s\) 的最短距离,可以预处理出来

时间复杂度为 \(\mathcal O(3^nn^2)\)

P6622 [省选联考 2020 A/B 卷] 信号传递 （状态的设计及优化）

题目

题解

按题意，我们暴力枚举这 \(m\) 个信号站的排列顺序，时间复杂度 \(\mathcal O((m!)\cdot n)\) 。

容易发现，题目给出的这个长度为 \(n\) 的序列S具体是什么不重要，重要的是，每一对信号站 \(i,j\) ，在 \(S\) 里作为相邻的位置，出现了多少次。也就是有多少个位置 \(p (1\leq p<n)\) 满足 \(S_p=i,S_{p+1}=j\) 。我们记这个数量为 \(\text{cnt}[i][j]\) 。

对于任意 \(i\neq j\)，\(\text{cnt}[i][j]\) 就表示要从信号站 \(i\) ，向信号站 \(j\)，进行多少次传递。设两个信号站的位置，分别为 \(\text{pos}[i]\),\(\text{pos}[j]\)，则它们会对答案产生的代价就是：

\[\begin{cases} \text{pos}[j]-\text{pos}[i]&&(\text{pos}[i]<\text{pos}[j])\\ k\cdot(\text{pos}[i]+\text{pos}[j])&&(\text{pos[i]}>\text{pos}[j]) \end{cases} \]

这样我们就干掉了 \(n\) 的限制,时间复杂度为 \(\mathcal O(n+(m!)\cdot m^2)\)

接下来我们有两种状压DP的状态设计

• 按位置考虑:设 \(f[s]\) 表示考虑完前 \(|s|\) 个数,填了集合 \(s\) 中位置
• 按值考虑:设 \(f[s]\) 表示考虑完前 \(|s|\) 个位置,填了集合 \(s\) 中的数

这是状压DP中两个极为常见的状态设计,而本题适用于第二种状态设计

为了方便转移,我们将点对的贡献拆解为单点的贡献,具体来说,假设我们考虑到第 \(\text{pos}\) 个位置:

• 对于一个前面的数 \(j\) ，从 \(i\) 到 \(j\) 产生的代价是：\(\text{pos}\cdot k\cdot \text{cnt}[i][j]\)。
• 对于一个前面的数 \(j\) ，从 \(j\) 到 \(i\) 产生的代价是：\(\text{pos}\cdot\text{cnt}[j][i]\) 。
• 对于一个后面的数 \(j\)，从 \(i\) 到 \(j\) 产生的代价是：\(-\text{pos}\cdot \text{cnt}[i][j]\) 。
• 对于一个后面的数 \(j\)，从 \(j\) 到 \(i\) 产生的代价是：\(\text{pos}\cdot k\cdot \text{cnt}[j][i]\) 。

转移方程就是

\[f[s+i]\leftarrow f[s]+\text{pos}\cdot \sum_{j\in s}(k\cdot\text{cnt}[i][j]+\text{cnt}[j][i])+\text{pos}\cdot\sum_{j\notin(s+i)}(-\text{cnt}[i][j]+k\cdot \text{cnt}[j][i]) \]

如果枚举 \(i\) ，再枚举 \(j\)，DP的时间复杂度 \(\mathcal O(2^mm^2)\)

我们继续优化。考虑只枚举 \(i\)。把 \(\text{pos}\)前的系数（也就是所有 \(j\) 的贡献之和），预处理出来，不妨记为：\(\text{cost}(s,i)\)。那么上述的转移式，也可以改写为：

\[f[s+i]\leftarrow f[s]+\text{pos}\cdot \text{cost}(s,i) \]

考虑预处理 \(\text{cost}(s,i)\)。首先，根据定义，\(i\notin s\)。

我们考虑，\(\text{cost}(s,i)\)，可以从“ \(s\) 去掉某个数”的状态，转移过来。我们不妨就去掉 \(j=\text{lowbit}(s)\)。那么，

\[\text{cost}(s,i)=\text{cost}(s-j,i)+(k\cdot \text{cnt}[i][j]+\text{cnt}[j][i])-(-\text{cnt}[i][j]+k\cdot \text{cnt}[j][i]) \]

这样转移是 \(\mathcal O(1)\) 的。所以预处理的时间复杂度为 \(\mathcal O(2^mm)\)，DP的时间复杂度也降为 \(\mathcal O(2^mm)\)。总时间复杂度 \(\mathcal O(n+2^mm)\)。但是 \(\text{cost}\) 数组会占用 \(\mathcal O(2^mm)\) 的空间，这无法承受。所以还要继续优化空间。

发现 \(\text{cost}\) 和 \(f\) 的转移，都是按集合从小到大进行的。所以我们不妨就按这个顺序，一边DP，一边求 \(\text{cost}\)。

对每个 \(s\)，我们把 \(\text{cost}(s,\dots)\) 视为一个大小为 \(m\) 的数组。当前的 \(s\)，我们先做DP转移，再拿 \(\text{cost}(s\dots)\) 数组去更新所有 \(\text{cost}(s'\dots )\)。发现更新完之后，\(\text{cost}(s,\dots)\) 这个大小为 \(m\) 的数组，就可以删掉

可以采取滚动数组的方式来实现,这样空间复杂度也符合要求了,可以通过本题

P1777 帮助 （普通状压dp）

题目

定义一个长度为 \(n\) 的序列的混乱度为序列中不相等连续段的个数,序列的极差不超过 \(7\) 现在你可以从序列中删掉 \(k\) 个值,求最小的混乱度

\(n,k\le 100\)

题解

首先离散化一下,得到一个新的数组 \(h\),\(h\) 的值域为 \(0\sim 7\)

设 \(f[i][j][k][l]\) 表示考虑到第 \(i\) 个位置,删去了 \(j\) 个数,选的数的集合为 \(k\) ,最后一个没有被删的数为 \(l\) ,那么显然有转移

• 如果第 \(i\) 个位置没有被删

\[f[i][j][k|(1<<h_i)][h_i]=\min\lbrace f[i-1][j][k][l]+[l=h_i] \rbrace \]

• 如果第 \(i\) 个位置被删

\[f[i][j+1][k][l]=\min\lbrace f[i-1][j][k][l]\rbrace \]

时间复杂度 \(\mathcal O(mk\times 8\times 2^8)\)

[BZOJ 1231] mixup2 （普通状压dp）

题目
\(\text{Farmer John}\)的\(N\)头奶牛中的每一头都有一个唯一的编号\(S_i\). 奶牛为她们的编号感到骄傲, 所以每一头奶牛都把她的编号刻在一个金牌上, 并且把金牌挂在她们宽大的脖子上. 奶牛们对在挤奶的时候被排成一支"混乱"的队伍非常反感.
如果一个队伍里所有两头相邻的奶牛的编号相差超过\(K\), 它就被称为是混乱的. 比如说，当\(N = 6, K = 1\)时\(1, 3, 5, 2, 6, 4\)就是一支"混乱"的队伍, 但是\(1, 3, 6, 5, 2, 4\)不是(因为\(5\)和\(6\)只相差\(1\)). 那么, 有多少种能够使奶牛排成"混乱"的队伍的方案呢?

题解

设 \(f[i][s]\) 表示考虑到第 \(i\) 头奶牛，奶牛的选取情况为 \(s\) 的方案数

转移时，如果当前枚举的 \(s\) 中不含 \(i\) 那么直接跳过，否则 \(f[i][s]\) 就可以从 \(f[j][s|(1<< (i-1))]\) 转移

P5933 [清华集训2012]串珠子 （连通图中的状压dp）

题目

给定 \(n\) 个点,两个点之间有 \(c[i][j]\) 条本质不同的边,求构成连通图的方案数

题解

直接维护连通是是困难的,那么正难则反

设 \(f[s]\) 表示点集为 \(s\) 且连通的方案数, \(g[s]\) 表示点集为 \(s\) 时任意连边的方案数, \(h[s]\) 表示点集为 \(s\) 时不连通的方案数

显然\(g[s]=\prod_{i,j\in s}(c[i][j]+1)\)

关于 \(h[s]\) ,可以任取 \(s\) 中的一个点 \(p\),设与 \(p\) 连通的子集为 \(s_1\) ,与 \(p\) 不连通的子集为 \(s_2\),那么 \(h[s]=f[s_1]\times g[s_2]\)

有\(f[s]=g[s]-h[s]\)

于是我们枚举子集转移即可

P2704 [NOI2001] 炮兵阵地 （多行影响的状压dp）

题目

在 \(N \times M\) ( \(N \le 100\) , \(M \le 10\) ) 的网格地图上部署炮兵部队。每一格可能是山地或平原，一个炮兵部队的攻击范围是长宽为 \(5\) 的十字形，炮兵部队只能部署在平原。

求在炮兵部队之间不能互相攻击的前提下，最多能部署多少炮兵
部队。

题解

考虑到

• 列数很小，可以状压。
• 每个炮兵可以向上影响两行，状压一行是不够的。
• 每个炮兵会向左右影响两个，每列放炮兵的方案不多。

于是我们可以状压两行,设 \(f[i][A][B]\),表示考虑到第 \(i\) 行,第 \(i-1\) 行的状态为 \(A\),第 \(i-2\) 行的状态为 \(B\) 的方案数

直接转移就行

CF453B Little Pony and Harmony Chest （根据题目性质减少压缩状态的大小）

题目

给定长为 \(n\) 的数组 \(a[]\)，要构造长为 \(n\) 的正数数组 \(b[]\)，要求 \(b[]\) 中的数两两互质，且最小化

\[val=\sum_{i=1}^n|a_i-b_i| \]

输出 \(b[]\) 。

\(1\le n \le 100, 1\le a_i\le 30\)

题解

若存在某 \(b_i\ge 59\)，那就不如把 \(b_i\) 改成 \(1\) ，因为 \(b_i-a_i\ge a_i-1\)，且改成\(1\)不影响互质。

所以 \(1\le b_i< 59\)。所有 \(b_i\) 的质因子分解式中，出现的质数只可能为 \(2,3,5,7,\cdots,53\)，共\(16\)个。

用状态 \(s\) 记录选了哪些质数。\(f(i,s)\) 表示考虑 \(a[1\sim i]\)，已经用过的质数集为 \(s\) 的最小 \(val\) 值。

枚举上一个的状态 \(s\)，再从 \(1\) 到 \(58\) 枚举现在要用哪个数，更新状态。记录 \(s\) 用于回溯

互质 （状压dp与背包的结合）

题目

有 \(n\) 个数，问这 \(n\) 个数里最多选出几个数，使得选出的数两两之间互质。

\(1\le n\le 1000\)
\(1\le 数字\le 1000\)

题解
\(33\)以内的质因数只有\(12\)个
一个\(1000\)以内的数，超过\(33\)的质因数只可能有一个

记一个状态\(s\)表示那\(12\)个质数的选择情况

• 对于任意一个数,只有\(33\)以内的质因数：这样的话，直接暴力转移即可

• 有\(33\)以上的质因数：将拥有相同的、大于\(33\)的质因数的数存成一组，分组背包转移

\(f[i][s]\)表示前\(i\)个数当中，选出了一些互质的数他们含有\(s\)里这些质因数的情况下，最多能选出的数的个数

复杂度\(\mathcal O(n2^{12})\)

BZOJ 5180 Cities （最小斯坦纳树）

题目

给定\(n\)个点，\(m\)条双向边的图。其中有\(k\)个点是重要的。每条边都有一定的长度。
现在要你选定一些边来构成一个图，要使得\(k\)个重要的点相互连通，求边的长度和的最小值。

\(k\le 5\)

\(n\le 10^5\)

\(1\le m\le 2\times 10^5\)

题解

首先，答案子图一定是一棵树，因为如果有环，那么一定可以断掉一条边使答案更优且保持图的联通

那么我们设\(f[i][s]\)表示以\(i\)为根，选了\(s\)中的点的最优答案

• 当点\(i\)度数为\(1\),设与它联通的点是\(j\),那么有转移

\[f[i][s]\leftarrow w_{i,j}+f[j][s] \]

• 当点\(i\)的度数大于\(1\)时，我们考虑枚举\(T\subseteq S\),那么有转移

\[f[i][s]\leftarrow f[i][S-T]+f[i][T] \]

上面那个转移很像最短路算法的三角不等式，使用\(dijkstra\)或\(spfa\)进行松弛操作转移\(\mathcal O(m\log m 2^k)\)

下面那个转移可以采取枚举子集的方法进行转移\(\mathcal O(n3^k)\)

与\(i\)联通的点每次转移都只会多一个，类似于背包，我们可以\(S\)从小到大枚举

每次松弛操作从\(j\)扩展到\(i\)时，如果\(i\)时关键点，没有算上\(i\)怎么办呢？不用管，因为后面一定有一次枚举子集转移时会把\(i\)算上

所以这个转移是正确，使用\(dij\)时间复杂度\(\mathcal O(m\log m 2^k+n3^k)\),不过这题的复杂度瓶颈并不在使用\(SPFA\)，因此使用\(SPFA\)会更快

[ATC 2230] Water Distribution （状压与最小生成树）

题目

在一个二维平面上有N个城市， 第\(i\)个城市的坐标是\((x_i,y_i)\) ， 一开始拥有的水量是\(a_i\)。
现在你可以从一个城市向另一个城市运送任意数量的水， 但水在运输过程中会有损耗， 具体而言如果从\(x\)城市运\(L\)水到\(y\)城市，最终\(y\)城市得到的水量是\(\max(0,L−dis(x,y))\)， 其中\(dis(x,y)\)指\(x\)和\(y\)城市间的欧几里得距离。 你可以多次进行这个操作。
你要使最终水量最少的城市水量尽量多， 求这个值，精度误差不超过 \(10^{-9}\).

\(1\le N\le 15\)

题解

枚举所有\(2^{15}\)次方种子集，对每一种子集求最小生成树检查一下是否能够送水，并求出最小的水量，记此时状态为\(f[s]\),\(s\)是此时点的选取情况，表示这个联通块的最小值为多少，时间复杂度\(\mathcal O(2^nn^2\log n)\)

然后对整个点集枚举子集的子集进行合并转移，时间复杂度是\(\mathcal O(3^n)\)的

总时间复杂度是\(\mathcal O(2^nn^2\log n+3^n)\)

[AGC 012E] Camel and Oases （根据题目性质巧妙选取压缩状态）

题目

数轴上有\(n\)个点，初始\(V=V_0\)，每次可以从一个点走到与他距离不超过\(V\)的点。当\(V>0\)时也可以让\(V=V/2\)并瞬移到任意一个点。
对于\(i=1\cdots n\)问从\(i\)号点出发能否遍历所有点。

\(1\le n,V_0\le 2×10^5\)

题解

首先\(V\)的取值只能有\(\log V_0\)种，对于每一种\(V\)的取值，它能够走的是一段段的连续的线段。所以我们可以考虑将图分成\(log V_0\)层连续的线段。

考虑一下用什么样的方式统计答案，我们可以考虑枚举第一层的每条线段\((l_i,r_i)\)，如果说存在一种方案使得从\(1\)开始覆盖到一个\(\ge li−1\)的位置，从\(n\)开始覆盖到一个\(\le r_i+1\)的位置，那么这段线段中的每一个点都是\(Possible\)的，否则就是\(Impossible\)

此时那个分层线段有一个性质：对于不同层之间的线段，它们相互之间要么上面的完全包含下面的，要么完全不相交

所以这时我们可以考虑维护\(lp[s],rp[s]\)分别表示从\(1\)开始向右可以扩展到的最右端和从\(n\)开始向左的最左端

通过状压每一层是否被选过，我们向中间选取连续的线段。假设我们现在要放第\(i\)层的线段，那么我们就要找到上一个状态扩展最远的位置，然后进行转移

\(st(i)\)表示当前我们选的那一层,定义两个过程：\(mr(i,x)\)表示在第i层的线段中，严格大于x的第一个右端点，\(ml(i,x)\)表示在第\(i\)层的线段中，严格小于x的最靠近\(n\)的右端点

那么转移如下

\[lp[st|St(i)]=\max \lbrace lp[st|St(i)],ml(i,lp[st])\rbrace\\ rp[st|St(i)]=\min\lbrace rp[st|St(i)],mr(i,rp[st]−1)\rbrace \]

处理完这个，如上文所言，我们就直接暴力枚举第一层的线段，然后\(check\)就可以了

[SRM 713] DFSCount （树上状压）

题目

给定一个\(n\)个点的简单无向图，问\(DFS\)序总共可能有多少种不同情况?

\(N\le 14\)
题解

设 \(f[i][s]\) ,表示以 \(i\) 为起点，走了 \(s\) 中点所产生的 \(\text{dfs}\) 序的个数

考虑 \(\text{dfs}\) 的过程，这显然是一棵树，并且只有把一棵子树中所有的点全部走完之后才会回溯到原来的点

那么对于状态 \(f[i][s]\) 的转移，我们可以使用并查集维护所有的连通块，当前点\(i\)可以转移到去掉\(i\)之后的所有连通块中，由于转移顺序比较神奇，所以我们直接记搜即可

CF1342F Make It Ascending （交换状态与值域）

题目

给定一个长度为 \(n\) 的序列 \(a\)，每次可以两个位置 \(i,j(i\neq j)\)，令 \(a_j\) 等于 \(a_i+a_j\) 并将 \(a_i\) 从序列中删除。

求将原序列变成严格单调上升的最少操作次数。

\(n\leq 15\)

题解

先将每个集合及其元素和预处理出来

设 \(f[i][p][s]\) 表示考虑了前 \(i\) 个集合,第 \(i\) 个集合剩下的那个元素位置是 \(p\),已经使用的数组成的集合是 \(s\) 时的最小操作次数

转移时枚举集合 \(s\) 的补集，并入第 \(i\) 个集合或者新建第 \(i+1\) 个集合。保证新加入的第 \(i+1\) 个集合中元素和大于第 \(i\) 个集合且有在 \(p\) 之后的元素。时间复杂度为 \(\mathcal{O}(n^23^n)\)

这道题涉及到方案的输出,因此给一个代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
const int N=16,inf=0x3f3f3f3f;
int T,n,a[N],f[N][N][1<<N],id[N];
struct node{
	int i,p,s;
}las[N][N][1<<N];
int sum[1<<N];
inline void update(node u,node v,int k)
{
	f[v.i][v.p][v.s]=min(f[v.i][v.p][v.s],k);
	if(f[v.i][v.p][v.s]==k) las[v.i][v.p][v.s]=u;
}
inline void solve()
{
	n=read();
	for(int i=0;i<n;++i) a[i]=read();
	for(int s=0;s<(1<<n);++s)//预处理处每个集合中数的和 
	{
		sum[s]=0;
		for(int i=0;i<n;++i)
			if(s&(1<<i)) sum[s]+=a[i]; 
	}
	for(int i=0;i<=n;++i)
		for(int p=0;p<=n;++p)
			for(int s=0;s<(1<<n);++s)
				f[i][p][s]=inf;
	f[0][0][0]=0;
	for(int i=0;i<n;++i)
		for(int p=0;p<n;++p)
			for(int s=0;s<(1<<n);++s)
			{
				if(f[i][p][s]==inf) continue;
				node u=(node){i,p,s};
				int ns=((1<<n)-1)^s;//求s的补集 
				for(int s0=ns;s0;s0=(s0-1)&ns)//枚举s的补集 
				{
					if(sum[s0]>f[i][p][s]&&(s0>>p)!=0)//s0的数的和大于上一个集合,并且有在p之后的数 
					{
						node v=(node){i+1,p+1+__builtin_ctz(s0>>p),s|s0};
						update(u,v,sum[s0]);//记录dp路径,方便输出答案 
					}
				}
			}
	node ans=(node){-1,-1,-1};
	for(int i=n;i>=1;--i)
	{
		for(int p=1;p<=n;++p)
			if(f[i][p][(1<<n)-1]!=inf)
			{
				ans=(node){i,p,(1<<n)-1};
				break;
			}
		if(ans.i!=-1) break;
	}
	printf("%d\n",n-ans.i);
	for(int i=0;i<n;++i) id[i]=i+1;
	while(ans.i!=0)//输出方案 
	{
		node tmp=las[ans.i][ans.p][ans.s];
		int s0=tmp.s^ans.s;
		for(int i=0;i<n;++i)
		{
			if((s0&(1<<i))&&i!=ans.p-1)
			{
				printf("%d %d\n",id[i],id[ans.p-1]);
				for(int j=i+1;j<n;++j) id[j]--;
			}
		}
		ans=tmp;
	}
} 
int main()
{
	T=read();
	while(T--) solve();
	return 0;
}

P2150 [NOI2015] 寿司晚宴 （根据质因子缩减范围）

题目

题解

我们进行根号分治

\(n\le 500\) 时，考虑小于 \(\sqrt{n}\) 的就那 \(8\) 个,而大于 \(\sqrt{n}\) 的质因子最多就只能有一个,所
以我们可以先用状压求出小于 \(\sqrt{n}\) 的那一部分质因子,然后枚举大于 \(\sqrt{n}\) 的质因子就可以了

具体来说,设 \(f[s_1][s_2]\) 表示两个人选的质因子集合分别为 \(s_1,s_2\) 时且让第一个人选大质因子的方案数,相应的 ,\(g[s_1][s_2]\) 表示让第二个人选大质因子的方案数,\(\text{dp}[i][j]\) 表示的是总方案数,显然有如下转移

\[\begin{cases} f[s_1|k][s_2]+=f[s_1][s_2]~~~(s_2\And k=0)\\ g[s_1][s_2|k]+=g[s_1][s_2]~~~(s_1\And k=0) \end{cases}\\ \text{dp}[s_1][s_2]=f[s_1][s_2]+g[s_1][s_2]-\text{dp}[s_1][s_2] \]

后面需要减去一个 \(\text{dp}[s_1][s_2]\) 是因为两者都不选的情况被统计了两次

时间复杂度 \(\mathcal{O}(n2^{16})\)

NOIP 四校联测 Day3 数字重组 （对极差的处理方法+增加维数）

题目

给一个长度为 \(n\) 的序列 \(a\),我们现在要将这 \(n\) 个数等分成 \(k\) 个集合,每个集合有 \(\frac{n}{k}\) 个元素 \((n~\text{mod}~k=0)\) ,每个集合中不能有重复的数,要求最大化集合中元素的极差之和

\(n\le 70\)

题解

数据范围很小,又是个跟集合划分有关的问题,明显是个状压dp

先来考虑怎么处理极差。

众所周知极差 \(=\max-\min\) ,所以我们从小到大考虑每个 \(a[i]\) ,将其放入每一个集合中。假设当前考虑到一个集合,我们要把一个数 \(x\) 放进去,当这个集合中为空时,就是对 \(\min\) 有了 \(x\) 的贡献,总极差 \(-x\) ;当这个集合只差一个就满时,就是对 \(\max\) 有 \(x\) 的贡献,总极差 \(+x\)

于是我们设 \(f[i][s]\) 表示考虑到第 \(i\) 个元素,集合的选取状况是 \(s\) ,注这个 \(s\) 可以使用 \(\text{vector}\) 存,由于我们存元素的集合本质相同,所以可以将 \(s\) 中的数量从小到大排序,方便转移

注意到题目中要求我们保证各个集合中没有重复元素,所以我们要增一维 \(j\) ,表示上一次放在了哪个位置(代码中表示的是上一次加入 \(a[i-1]\) 的那个集合中数的个数)。

然后特判+转移即可,详见代码

本题的复杂度证明是难点,注意到每个状态都能看作从 \((0, 0)\) 出发往右往上走到达 \((k,\frac{n}{k})\)
的折线,由此可知状态数为 \(\binom{k+\frac{n}{k}}{k}\le \binom{2\sqrt n}{\sqrt n}\)

所以总的时间复杂度是 \(\mathcal{O}\left(nk \binom{2\sqrt{n}}{\sqrt{n}}\right)\)

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=110,M=60010,inf=1e18;
vector<int> S[M];
map<vector<int>,int> mp;
int n,k,tmp[N],cnt,sum[M],a[N];
int f[2][M][N];
inline void init(int x)
{
	if(x>k)
	{
		++cnt;
		for(int i=1;i<=k;++i)
			S[cnt].push_back(tmp[i]),sum[cnt]+=tmp[i];
		mp[S[cnt]]=cnt;
		return;
	}
	for(int i=tmp[x-1];i<=n/k;++i)
	{
		tmp[x]=i;
		init(x+1);
	}
}
signed main()
{
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	n=read();k=read();
	for(int i=1;i<=n;++i) a[i]=read();
	sort(a+1,a+1+n);
	init(1);//预处理选择的状态 
	memset(f,inf,sizeof(f));
	f[0][1][0]=0;
	for(int i=1;i<=n;++i)
	{
		for(int s=1;s<=cnt;++s)
		{
			if(sum[s]!=i) continue;
			for(int j=0;j<=n/k;++j)
				f[i&1][s][j]=inf;
		}
		for(int s=1;s<=cnt;++s)//s-->x 
		{
			if(sum[s]!=i-1) continue;
			for(int j=0;j<=n/k;++j)
			{
				for(int p=0;p<k;++p)
				{
					if(p<k-1&&S[s][p]==S[s][p+1]) continue;//先填后面 
					if(S[s][p]==n/k) continue;//当前位置已满 
					vector<int> nw=S[s];
					++nw[p];//当前位置新增一员 
					if(a[i]==a[i-1])
					{
						if(S[s][p]>j) continue;
						int x=mp[nw];//对应的状态编号
						int val=0;
						if(S[s][p]==n/k-1) val+=a[i];//最大的 
						if(S[s][p]==0) val-=a[i];//最小的 
						f[i&1][x][S[s][p]]=min(f[i&1][x][S[s][p]],f[(i&1)^1][s][j]+val);
					}
					else
					{
						int x=mp[nw];
						int val=0;
						if(S[s][p]==n/k-1) val+=a[i];
						if(S[s][p]==0) val-=a[i];
						f[i&1][x][S[s][p]]=min(f[i&1][x][S[s][p]],f[(i&1)^1][s][j]+val);
					}
				}
			}
		}
	}
	printf("%lld\n",f[n&1][cnt][n/k-1]);
	return 0;
}

SDOI 一轮省集 哈密顿路 （交换答案与状态+无向图哈密顿路性质+lowbit优化转移）

题目

给定由 \(n\) 个点组成的无向图，对于图中得每一对点 \(x,y\) 判断是否存在以它们为起点终点的哈密顿路

\(n\leq 24\)

题解

设 \(f[x][y][S]\) 表示是否存在以 \(x\) 为起点，当前走到点 \(y\) ，走过的点构成的集合是 \(S\) 时的路径，这个东西的空间是 \(\mathcal O(n^22^n)\) ，时间是 \(\mathcal O(n^32^n)\) 的，显然无法通过本题

我们来思考一下这个 \(\text{dp}\) ，首先 \(x\) 没有参与 \(\text{dp}\) 的转移，因此这一维空间可以去掉， 对于每个 \(x\) 分别初始化然后转移即可。然后这种可行性 \(\text{dp}\) 显然可以考虑交换答案与状态的，于是我们更改 \(\text{dp}\) 状态为 \(f[S]=T\) 表示当前经过点集 \(S\) ，现在所处的位置可以是 \(T\) 。这个做法的空间复杂度为 \(\mathcal O(2^n)\) ，时间复杂度为 \(\mathcal O(n^22^n)\) ,仍然无法通过本题

注意到无向图哈密顿路的一个性质——对于图中一点 \(i\) ，如果 \(x\) 到 \(y\) 之间存在哈密顿路，即一定经过点 \(i\) ，路径就可以写成 \(x\rightarrow i\rightarrow y\) ，由于是无向图，上面那个就等价于找 \(i\rightarrow x,i\rightarrow y\) 这两条路径，两条路径不交且并集是全集，于是我们就可以钦定起点为任意一点（我选择了 \(n\) 这个点），转移时，我们可以考虑预处理出 \(\text{nxt}[S]=T\) 表示从点集 \(S\) 中出发可以到达的点组成的集合 \(T\) ，这里复杂度是 \(\mathcal O(n2^n)\) 的。转移即从 \(\text{nxt}[S]\) 在 \(S\) 中的补集中转移到 \(S\) ，求出我们上文所说的 \(f[S]\) ，最后利用 \(f[S]\) 更新出答案，时间复杂度降为 \(\mathcal O(n2^n)\) ,可以通过本题。

值得注意的是，我们在枚举经过 \(S\) 集合中的点最终停留的点的位置，即 \(f[S]\) 时，可以使用 \(\text{lowbit}\) 来枚举停留的位置

具体代码如下

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
const int N=24;
int n,m,ans[N],g[N][N];
char s[N];
int f[1<<N],nxt[1<<N];
inline int getS(int x)
{
	return (1<<x);
}
inline int lowbit(int x)
{
	return x&(-x);
}
int main()
{
	//freopen("hamilton.in","r",stdin);
	//freopen("hamilton.out","w",stdout);
	n=read();m=getS(n-1);
	for(int i=0;i<n;++i)
	{
		scanf("%s",s);
		for(int j=0;j<n;++j)
			if(s[j]=='1') nxt[getS(i)]^=getS(j);
	}
	for(int i=0;i<n;++i)
		for(int mk=0;mk<(1<<n);++mk)
		{
			if((mk>>i)&1) nxt[mk]|=nxt[mk^getS(i)];
		}
	for(int i=nxt[getS(n-1)];i;i-=lowbit(i)) f[lowbit(i)]=lowbit(i);
	for(int i=1;i<m;++i)
		for(int j=0;j<n-1;++j)
		{
			if((i>>j)&1) continue;
			if((nxt[f[i]]>>j)&1)
				f[i|getS(j)]|=getS(j);
		}
	ans[n-1]=f[m-1];
	for(int i=1;i<m;++i)
		for(int j=f[i];j;j-=lowbit(j))
		{
			int cnt=__builtin_ctz(j);
			ans[cnt]|=f[(m-1)^i];
		}
			
	for(int i=0;i<n-1;++i)
		for(int j=i+1;j<n;++j)
			if((ans[j]>>i)&1) g[i][j]=g[j][i]=1;
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
			printf("%d",g[i][j]);
		puts("");
	}
		
	return 0;
}

Atcoder Beginner Contest 319 F （贪心+图上状压）

题意

你在一棵有 \(n\) 个点的树上战斗，起初你的战斗力是 1 ，树上有 \(k\) 个点是药剂，其余都是怪物。

对于第 \(i\) 个点有两个值 \(s_i,g_i\)

1. 如果这个点是怪物，那么如果你当前的战斗力不小于 \(s_i\)，你就可以增加 \(g_i\) 的战斗力（注意这里比那个经典贪心简单，不用扣血）
2. 如果这个点是药剂，那么你当前的战斗力就会乘上 \(g_i\)

请判断你是否可以杀掉所有怪物

\(n\le 500\)
\(s_i,g_i\le10^9\)
\(k\le 10\)

题解

假设没有药剂，那么考虑贪心，我们就开一个优先队列，每次走 \(s_i\) 小的那个怪物就行了

而如果有药剂，我们发现，如果能加那就一定要先加，先加再乘一定比先乘后加更优

那么我们就每次按照第一个贪心先加，走不动了就找那个 \(g_i\) 最小的药剂，知道能走动为止，这样就可以了

吗？

考虑我们目前有两个可以使用的药剂，他们的回复量分别是 \(a,b~(a<b)\) ，如果说，我们当前只用一个 \(b\) 可以走动，只用 \(a\) 不能走动，但按照我们上面的贪心，我们会先用了 \(a\) ，再用了 \(b\) ，由先加后乘一定比先乘后加更优，我们这里显然浪费了 \(a\) 的贡献，那么这个贪心就是错的

但是天无绝人之路，注意到原题中 \(k\le 10\) ，也就是药剂的数量很少，于是我们就可以考虑枚举药剂的顺序，按照顺序喝药，再跑上面的贪心，这样就是对的，但是时间复杂度 \(\mathcal O(k!nk\log n)\) ，我们无法接受

所以考虑状压，设 \(f[S]\) 表示选了集合 \(S\) 中的药剂后的战斗力最大值可以是多少，每次将当前集合可以连接到的药剂给记下来，并分别考虑加入每一个药剂，转移即可

时间复杂度 \(\mathcal O(2^knk\log n)\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=510;
ll f[1<<10];
int n,m;
struct Edge{
	int v,nxt;
}edge[N];
int cnt,head[N];
inline void add_edge(int u,int v)
{
	edge[++cnt].v=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
int s[N],g[N],iq[N];
const ll inf=1e9+10;
struct node{
	int u,w;
	bool operator < (const node &x) const{return x.w<w;}
};
int main(){
	memset(f,-1,sizeof(f));
	scanf("%d",&n);
	for(int i=2,fa,ty;i<=n;++i)
	{
		scanf("%d%d%d%d",&fa,&ty,&s[i],&g[i]);
		add_edge(fa,i);
		if(ty==2) iq[i]=++m;
	}
	priority_queue<node>q;
	q.push((node){1,s[1]});
	ll val=1;
	while(!q.empty()&&val>=q.top().w){
		int u=q.top().u;q.pop();
		val+=g[u];
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int v=edge[i].v;
			if(!iq[v])
				q.push((node){v,s[v]});
		}
	}
	f[0]=val;
	for(int S=0;S<(1<<m);++S)
		if(f[S]>=0)
		{
			f[S]=min(f[S],inf);
			while(!q.empty())q.pop();
			q.push((node){1,s[1]});
			vector<int> tmp;
			while(!q.empty()&&f[S]>=q.top().w)
			{
				int u=q.top().u;q.pop();
				for(int i=head[u];i;i=edge[i].nxt)
				{
					int v=edge[i].v;
					if(!iq[v]||((S>>(iq[v]-1))&1))
						q.push((node){v,s[v]});
					else tmp.emplace_back(v);
				}	
				
			}
			if(S==(1<<m)-1)
			{
				if(q.empty()) puts("Yes");
				else puts("No");
				return 0;
			}
			for(int x:tmp)
			{
				ll np=min(inf,f[S]*g[x]);
				int T=S|(1<<(iq[x]-1));
				priority_queue<node> q2=q;
				for(int i=head[x];i;i=edge[i].nxt)
				{
					int v=edge[i].v;
					q2.push((node){v,s[v]});
				}
				while(!q2.empty()&&np>=q2.top().w)
				{
					int u=q2.top().u;q2.pop();
					np+=g[u];
					for(int i=head[u];i;i=edge[i].nxt)
					{
						int v=edge[i].v;
						if(!iq[v]) q2.push((node){v,s[v]}); 
					}
						
				}
				f[T]=max(f[T],np); 
			}
		}
	return puts("No"),0;
}

标签：状态,le,int,text,压缩,枚举,mathcal,复杂度,dp
From： https://www.cnblogs.com/starroadxyz/p/17578184.html