「题解」「省选联考 2020 A/B 卷」信号传递

分析

首先转化一下题意。

\[c(i,j)=\left\{\begin{array}{l}(i,j)\space在所有\space(s_i,s_{i+1})\space中出现的次数,i\not=j\\0,i=j\end{array}\right. \]

设重排后的 \(i\) 号信号站是原来的 \(p_i\) 号信号站。

\[w(x,y)=\left\{\begin{array}{l}y-x,x\le y\\k\times(x+y),x>y\end{array}\right. \]

\[\sum_{i=1}^n\sum_{j=1}^nc(p_i,p_j)\times w(i,j) \]

的最小值。

考虑拆开贡献。上式可以拆成 \(\sum_{i=1}^ni\times t(i)\)，其中

\[t(x)=\sum_{i=1}^{x}(c(p_x,p_i)+k\times c(p_i,p_x))+\sum_{i=x+1}^n(k\times c(p_x,p_i)-c(p_i,p_x)) \]

发现 \(t(i)\) 只和 \(p_1,p_2,\ldots p_i\) 构成的集合有关，与其顺序无关，所以可以状压。

设 \(g(s,i)\) 表示 \(p\) 的前 \(|s|\) 项的集合为 \(s\) 且 \(p_{|s|}=i\) 时 \(t(|s|)\) 的值。

设 \(f(s)\) 表示 \(p\) 的前 \(|s|\) 项的集合为 \(s\) 时 \(\sum_{i=1}^{|s|}i\times t(i)\) 的最小值。

枚举 \(p_{|s|}\) 转移

\[f(s)=\min\{f(s-\{i\})+|s|\times g(s,i)\},i\in s \]

只需要预处理出 \(g\) 的值就可以 \(O(m\times 2^m)\) 转移。列一下 \(g(s,i)\) 的表达式：

\[g(s,i)=\sum_{x\in s}(c(x,i)+k\times c(i,x))+\sum_{x\not\in s}(k\times c(x,i)-c(i,x)) \]

提出 \(s\) 中的一个元素 \(x\)，\(g(s,i)\) 可以 \(O(1)\) 从 \(g(s-\{x\},i)\) 转移。

所以预处理 \(g\) 的时间复杂度也是 \(O(m\times 2^m)\)。做完了？

并没有。这个算法的空间复杂度也是 \(O(m\times 2^m)\)，开不下。

优化空间的方法有很多。讲一个我最喜欢的。

二进制顺序枚举 \(s\)，强制 \(g(s)\) 从 \(g(s-\operatorname{lowbit}(s))\) 转移。

有性质：\(s-\operatorname{lowbit}(s)\) 是小于 \(s\) 且大小为 \(|s|-1\) 的最大的集合。

所以在集合大小相同的状态中，只有最近枚举到的可能向后更新。只需储存这些状态。

具体地，设 \(h(w,i)\) 表示设最近枚举到的大小为 \(w\) 的集合为 \(s\)，\(g(s,i)\) 的值。

空间复杂度优化为 \(O(2^m)\)。