题解 P6622 【[省选联考 2020 A/B 卷] 信号传递】

BJpers2 · 2020-06-27 10:48:51 · 题解

为表述方便，以下称信号站为点，传输序列中相邻两个点之间连一条从前往后的有向边。

一个显而易见的结论

设边x\rightarrow y的代价为（x,y是坐标）

显然可以将此代价分到各个点上来累加。具体来说，对于最终在坐标为x的点，序列中每有一条x\rightarrow y的边，若x\le y则付出k的代价，否则付出-1的代价。同理对于y\rightarrow x的边分别付出1和k的代价。最终总代价等于每个点的代价分别乘其坐标再求和。

然而我考场上并没有想到这个显而易见的结论，只拿了30分，我太菜了。

一个基本的做法

容易发现在上述转化下，一个点的贡献只与坐标在其前面的点集有关，只序预处理出g(i,S)表示i号点前面的点集为S时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队长的题解。

方法三：巧妙折半

注意到，我们没有必要考虑i\in S的g(i,S)。这样对于每个i而言只有2^{22}种S需要计算，总量减少了一半。

空间开销与方法一致，为368\text{M}。这个方法实现非常优美，而且思路直接，是本人第二喜欢的算法。

#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分）。优点在于，不但空间优秀，而且实现十分无脑，是本人最喜欢的算法。

#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)。

这样时空复杂度不变，但常数得到了很大优化，洛谷不吸氧可过。

#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_1和g_2的空间都得到了开根级别的优化，空间开销相对于f来说已经可以忽略不计。其余部分照做即可。

缺点是代码难度（相对方法四、五来说）比较高，优点在于常数非常小，现在luogu和LOJ的最优解都是这种做法（应该是同一个人）。