毒瘤状态压缩。

题目链接：联合省选 2020 B D2T2/Luogu P6622/LibreOJ 3302。

注意：本题与 联合省选 2020 A D2T1 一致，我水了两篇博客。

题目

题目描述

一条道路上从左至右排列着 $m$ 个信号站，初始时从左至右依次编号为 $1,2,\cdots,m$，相邻信号站之间相隔 $1$ 单位长度。每个信号站只能往它右侧的任意信号站传输信号（称为普通传递），每单位长度距离需要消耗 $1$ 单位时间。道路的最左侧有一个控制塔，它在最左侧信号站的左侧，与其相隔 $1$ 单位长度。控制塔能与任意信号站进行双向信号传递（称为特殊传递），但每单位长度距离需要消耗 $k$ 个单位时间。对于给定的长度为 $n$ 的信号传递序列 $S$，传递规则如下：

1. 共 $n-1$ 次信号传递，第 $i$ 次信号传递将把信号从 $S _ i$ 号信号站传递给 $S _ {i+1}$ 号。
2. 若 $S _ {i+1}$ 号信号站在 $S _ i$ 号右侧，则将使用普通传递方式，从 $S _ i$ 号直接传递给 $S _ {i+1}$ 号。
3. 若 $S _ {i+1}$ 号信号站在 $S _ i$ 号左侧，则将使用特殊传递方式，信号将从 $S _ i $ 号传递给控制塔，再由控制塔传递给 $S _ {i+1}$ 号。
4. 若 $S _ i=S _ {i+1}$，则信号无须传递。

阿基作为大工程师，他能够任意多次交换任意两个信号站的位置，即他能够重排信号站的顺序，这样会使得 $S$ 消耗的传递时间改变。现在阿基想知道，在他重排信号站顺序后，$S$ 所消耗的传递时间最小能是多少。

数据范围

时空限制

题目编号	时间限制	空间限制
联合省选 2020 B D2T2	$2\text{s}$	$512\text{MiB}$

题解

本题有部分分做法。

解法 A（暴力）

$30\%$ 的数据：$m\leq 8,n\leq 100$。

---

枚举 $1\sim m$ 的全排列，然后统计答案求最小值即可。

时间复杂度为 $\Theta(n\times m!)$，期望得分 $30$ 分。

解法 B（状态压缩动态规划）

设 $x$ 所在的位置为 $p _ x$，那么如果存在一次信号传递为：$x\to y$，花费代价为：

$$
\begin{cases}
p_y-p_x&p_x<p_y\\
k(p_x+p_y)&p_x>p_y
\end{cases}$$

设 $f _ S$ 表示当前已经用 $S$ 中的信号站填上了 $1\sim |S|$ 这些位置，那么转移时已知当前信号站的位置和这个信号站与其他信号站的相对大小关系。

预处理 $e _ {x,y}$ 表示 $x$ 到 $y$ 的信号传递次数后，就可以 $\Theta(m)$ 地计算新加入的信号站对答案的贡献
$$f_{S}=\min _ {x\in S}\{{f_{S-x}+|S|\sum_{i\in S-x}(ke_{x,i}+e_{i,x})+|S|\sum_{i\notin S}(ke_{i,x}-e_{x,i})\}}$$

时间复杂度为 $\Theta(2^mm^2)$，期望得分 $60$ 分。

解法 C（优化）

进一步观察转移的式子，可以发现转移中 $p_x$（在上式中等于 $|S|$） 的系数取决于 $S$ 与 $x$ 间入边和出边的数量。

因此，设 $to _ {S,x}$ 表示在转移 $f _ {S}\to f _ {S+x}$ 中 $p _ x$ 的系数，则 $to _ {S+x,y}$ 可以在已知 $to _ {S,y}$ 的情况下 $\Theta(1)$ 计算出来：

$$to_{S+x,y}=to_{S,y}+(1-k)e_{x,y}+(1+k)e _ {y,x}$$

时间复杂度为 $\Theta(2^mm)$，期望得分 $80$ 分。

解法 D（优化）

解法 C 的空间复杂度过高，需要继续优化。

观察到转移的时候只会从 $1$ 个数较少的状态转移到较大的状态，因此可以按 $1$ 的个数进行滚动数组优化。

时间复杂度 $\Theta(2^m+m\binom{m}{\frac{m}{2}})$，期望得分 $100$ 分。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X7FFFFFFF
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXM=23;
const int MAXSIZE=1.4e6;

int n,m,k;
int f[1<<MAXM];
int E[MAXM][MAXM],to[2][MAXSIZE][MAXM],w[2][MAXSIZE];

inline void Add_Edge(reg int u,reg int v){
    if(u!=v)
        ++E[u-1][v-1];
    return;
}

inline int cmin(reg int &a,reg int b){
    return a>b?a=b:a;
}

inline void ins(reg int* a,reg int x,reg int *b){
    for(reg int i=0;i<m;++i)
        b[i]=a[i]+E[x][i]*(1-k)+E[i][x]*(k+1);
    return;
}

int main(void){
    n=read(),m=read(),k=read();
    reg int S=((1<<m)-1);
    reg int last=0;
    for(reg int i=1;i<=n;++i){
        reg int x=read();
        if(last)
            Add_Edge(last,x);
        last=x;
    }
    for(reg int i=1;i<=S;++i)
        f[i]=INF;
    for(reg int i=0;i<m;++i)
        for(reg int j=0;j<m;++j)
            to[0][0][j]+=E[i][j]*k-E[j][i];
    reg int cnt=0,tot=0;
    reg int lastptr=0,ptr;
    for(reg int x=1;x<=m;++x){
        tot=-1;
        ptr=lastptr^1;
        for(reg int i=0;i<=cnt;++i)
            for(reg int j=0;j<m;++j)
                if(!(w[lastptr][i]>>j)){
                    w[ptr][++tot]=1<<j|w[lastptr][i];
                    ins(to[lastptr][i],j,to[ptr][tot]);
                }
        for(reg int i=0;i<=cnt;++i)
            for(reg int j=0;j<m;++j)
                if(~w[lastptr][i]>>j&1)
                    cmin(f[1<<j|w[lastptr][i]],f[w[lastptr][i]]+to[lastptr][i][j]*x);
        lastptr=ptr,cnt=tot;
    }
    printf("%d\n",f[S]);
    return 0;
}