题解 P6622 【[省选联考 2020 A/B 卷] 信号传递】
BJpers2
2020-06-27 10:48:51
为表述方便，以下称信号站为点，传输序列中相邻两个点之间连一条从前往后的有向边。
### 一个显而易见的结论
设边$x\rightarrow y$的代价为（$x,y$是坐标）
$$
\begin{cases}
y-x & x\le y \\
kx+ky & x>y
\end{cases}
$$
显然可以将此代价分到各个点上来累加。具体来说，对于最终在坐标为$x$的点，序列中每有一条$x\rightarrow y$的边，若$x\le y$则付出$k$的代价，否则付出$-1$的代价。同理对于$y\rightarrow x$的边分别付出$1$和$k$的代价。最终总代价等于每个点的代价分别乘其坐标再求和。
~~然而我考场上并没有想到这个显而易见的结论，只拿了30分，我太菜了。~~
### 一个基本的做法
容易发现在上述转化下，一个点的贡献只与坐标在其前面的点集有关，只序预处理出$g(i,S)$表示$i$号点前面的点集为$S$时$i$对答案的贡献，即可用以下转移求出答案：
$$
f(S)+g(i,S)\rightarrow f(S\cup\{i\})
$$
如果暴力计算$g(i,S)$（枚举$i,S$以及$S$中的元素$j$），时间复杂度为$O(m^22^m)$。
但显然可以从小到大枚举$S$递推$g$，此时时间复杂度优化为$O(m2^m)$，但空间复杂度也为$O(m2^m)$，如果开$23\times 2^{23}=192,937,984$的$\text{int}$数组，将花费$736\text{M}$的空间，不可承受。（因为主要的空间瓶颈是$g$数组，为方便计算，以下都只计算$g$的空间开销）
### 优化
接下来就是大家喜闻乐见的卡空间环节。其实到了这一步基本上就是各凭本事了，做法也不是唯一的。就我所知大概有七种做法，本质不同的有四种。
#### 方法一：强行折半
注意到$g$数组的递推具有比较强的拓扑性，即$g(i,S)$值会转移到某个大小恰比$S$大$1$的集合$T$。$f$同理。
于是我们可以分两步走，先求出$|S|\le 11$的所有$g(i,S)$，并求出所有相应$|S|\le 12$的$f(S)$；然后清空$g$数组（但保留$|S|$恰为$11$的），把空间腾出来存储所有$|S|>12$的$g$。
这样每时每刻我们只需存储大约一半的$g$，空间大概是$23\times 2^{22}\times 4\text{B}=368\text{M}$，可以承受。
本方法在任何角度都有完全优于它的算法存在，只是作为一个引入。
#### 方法二：滚动数组
原理与方法一相似，但分层更为细致。我们严格按照$|S|$单调不降处理所有的$f$和$g$，用滚动数组实现$g$的递推。
那么我们同一时刻最多需要存储的$g(i,S)$状态个数取决于哪个大小的集合最多，根据常识可知有分别有$\binom{23}{12}$个集合大小为$11$和$12$，是最多的。
因此空间开销为$2\times 23\times \binom{23}{12}\times 4\text{B}\approx 237\text{M}$。
缺点是滚动数组是三维的，寻址十分缓慢。优势在于空间**比较**小。详见[Fuyuki队长的题解。](https://www.luogu.com.cn/blog/fuyuki/solution-p6622)
#### 方法三：巧妙折半
注意到，我们没有必要考虑$i\in S$的$g(i,S)$。这样对于每个$i$而言只有$2^{22}$种$S$需要计算，总量减少了一半。
空间开销与方法一致，为$368\text{M}$。这个方法实现非常优美，而且思路直接，是本人第二喜欢的算法。
```cpp
#include<iostream>
#include<cstdio>
#define gmi(a,b) a=a<b?a:b
#define FOF(i,a,b) for(int i=a;i< b;i++)
using namespace std;
const int M=23,N=1<<M,INF=1e9;
int n,m,K,x=-1,y,z,w,L,R;
int lg[N],sz[N],f[N],g[M][M],h[M][N>>1];
int main(){
scanf("%d%d%d",&n,&m,&K);L=1<<m;R=L>>1;lg[0]=-1;
while(n--) scanf("%d",&y),~x?++g[x][--y]:--y,x=y;
FOF(i,1,L) lg[i]=lg[i>>1]+1,sz[i]=sz[i>>1]+(i&1);
FOF(i,0,m){
FOF(j,0,m)if(i^j) h[i][0]+=g[j][i]*K-g[i][j];
FOF(j,1,R) y=j&-j,z=lg[y],z+=z>=i,h[i][j]=h[i][j^y]+g[i][z]*(1+K)+g[z][i]*(1-K);
}
FOF(i,1,L)for(f[i]=INF,x=i;y=x&-x;x^=y)
z=lg[y],w=i^y,gmi(f[i],f[i^y]+h[z][w&y-1|w>>z+1<<z]*sz[i]);
cout<<f[L-1]<<'\n';
}
```
#### 方法四：经典结论
> 二进制从$0$数到$n$，所有比特位变化的总次数为$O(n)$。
我们直接去掉$g$的$S$那一维。然后按二进制数大小（而不是集合大小）顺序枚举$S$，并按照$S+1$相对$S$的变化暴力修改$g$。
根据上述结论，我们对每个比特位的变化，修改$g$的代价是$O(m)$。那么总修改代价就为$O(m2^m)$，时间复杂度正确。
更强悍的是，这种做法只需要$O(2^m)$的空间，每多开一个数组只消耗$32\text{M}$的空间，总空间可以限制在$100\text{M}$以内。
缺点不是很明显，硬要说的话就是跑得还不够快（洛谷上不吸氧至多$85$分）。优点在于，不但空间优秀，而且实现十分无脑，是本人最喜欢的算法。
```cpp
#include<iostream>
#include<cstdio>
#define gmi(a,b) a=a-b>>31?a:b
#define FOF(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int M=23,N=1<<M;
int n,m,K,x,y,z,w,s,L,R;
int f[N],g[M][M],h[M],c[M][M],lg[N],sz[N];
int main(){
scanf("%d%d%d",&n,&m,&K),x=-1;
while(n--) scanf("%d",&y),~x?++g[x][--y]:--y,x=y;
FOF(i,0,m)FOF(j,0,m)if(i^j)
h[i]+=g[j][i]*K-g[i][j],c[i][j]=g[i][j]*(1+K)+g[j][i]*(1-K);
R=1<<m;L=R-1;lg[0]=-1;
FOF(i,1,R) sz[i]=sz[i>>1]+(i&1),lg[i]=lg[i>>1]+1,f[i]=1e9;
FOF(i,0,L){
s=sz[i]+1;
for(x=L^i ;y=x&-x;x^=y) w=f[i]+h[lg[y]]*s,gmi(f[i|y],w);
for(x=i^i+1;y=x&-x;x^=y){
w=lg[y];
if(y&i) FOF(j,0,m) h[j]-=c[j][w];
else FOF(j,0,m) h[j]+=c[j][w];
}
}
cout<<f[L]<<'\n';
}
```
#### 方法五：巧妙递推
依旧是沿着方法四的思路，二进制顺序枚举$S$，考虑$w(i,j)$表示$j$的前面是「最近的被枚举的大小为$i$的集合」时，$j$对答案的贡献。
容易证明，枚举到$S$时，$w(|S|-1,j)$恰好存的是$g(j,S-\text{lowbit}(S))$。因此可以直接转移得到$w(|S|,j)$。
这样时空复杂度不变，但常数得到了很大优化，洛谷不吸氧可过。
```cpp
#include<iostream>
#include<cstdio>
#define gmi(a,b) a=a-b>>31?a:b
#define FOF(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int M=23,N=1<<M;
int n,m,K,x,y,z,s,L,R;
int f[N],g[M][M],w[M][M],c[M][M],lg[N],sz[N];
int main(){
scanf("%d%d%d",&n,&m,&K),x=-1;
while(n--) scanf("%d",&y),~x?++g[x][--y]:--y,x=y;
FOF(i,0,m)FOF(j,0,m)if(i^j)
w[0][i]+=g[j][i]*K-g[i][j],c[i][j]=g[i][j]*(1+K)+g[j][i]*(1-K);
R=1<<m;L=R-1;lg[0]=-1;
FOF(i,1,R) sz[i]=sz[i>>1]+(i&1),lg[i]=lg[i>>1]+1,f[i]=1e9;
FOF(i,0,L){
z=lg[i&-i];
if(s=sz[i]) FOF(j,0,m) w[s][j]=w[s-1][j]+c[j][z];//只有这里和方法四不同
for(x=L^i;y=x&-x;x^=y) z=f[i]+w[s][lg[y]]*(s+1),gmi(f[i|y],z);
}
cout<<f[L]<<'\n';
}
```
#### 方法六：登峰造极
注意到，方法四、五的空间可以利用方法二的思想进一步优化，可以将$f$个数组进行滚动。这样一来$sz$数组就没有了存在的意义，而$lg$数组只会调用$2$的幂，可以不用开那么大的空间。
此时$f$是空间的唯一瓶颈，滚动优化之，空间达到了$2\times \binom{23}{12}\times 4\text{B}\approx 10\text{M}$。
可能有人觉得出题人卡空间，但殊不知出题人给我们$512\text{M}$已经是最大的宽容。（估计来个$16\text{M}$就真成经典了
本方法没有经过实现，但理论分析表明，本算法受滚动数组和$\log_2$被阉割的影响，运行效率很可能不如方法四。(当然你用ctz我也没话说)
#### 方法七：分块
又是一个很粗暴的思路，既然难以一次性存储$i$对所有集合的代价，那就把集合$S$拆成前$12$位和后$11$位两部分，即
$$
g(i,S)=g_1(i,S\cap[0,11])+g_2(i,S\cap[12,22])
$$
这样$g_1$和$g_2$的空间都得到了开根级别的优化，空间开销相对于$f$来说已经可以忽略不计。其余部分照做即可。
缺点是代码难度（相对方法四、五来说）比较高，优点在于常数非常小，现在luogu和LOJ的最优解都是这种做法（应该是同一个人）。