Luogu

LOJ

分析

考虑从 $x$ 传递到 $y$ 的代价，显然有
$$
w(x,y)=\begin{cases}p_y-p_x,&p_x\leq p_y\\k(p_x+p_y),&\mathrm{otherwise}\end{cases}
$$
可以发现这个东西是可以拆到每个信号站计算的。

考虑 DP。设 $f_S$ 表示 $S$ 中的信号站的位置是 $1\cdots |S|$ 时的最小代价。

设 $c_{i,j}$ 表示从 $i$ 传递到 $j$ 的次数，可以得到转移
$$
f_{S}=\min_{x\in S}\left\{f_{S-x}+|S|\sum_{i\in S-x}(k\times c_{x,i}+c_{i,x})+|S|\sum_{i\notin S}(k\times c_{i,x}-c_{x,i})\right\}
$$
直接暴力 DP 是 $\mathcal{O}(m^22^m)$ 的，并过不了。

考虑先预处理出 $g(x,S)=\sum_{i\in S-x}(k\times c_{x,i}+c_{i,x})+\sum_{i\notin S}(k\times c_{i,x}-c_{x,i})$。容易得到有
$$
g(x,S)=g(x,S-y)+(1+k)c_{x,y}+(1-k)c_{y,x}
$$
这样子就可以 $\mathcal{O}(m2^m)$ 预处理 $g(x,S)$ 和求 $f_S$，总时间复杂度 $\mathcal{O}(m2^m)$。

然而存 $g$ 需要 736MB 空间，并开不下。

但是可以发现，我们只需要求 $x\in S$ 的 $g(x,S)$，所以我们只需要对每个 $x$ 求 $2^{m-1}$ 个 $g(x,S)$，这样子就只需要 368MB 空间了。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=23+5;

int n,m,k,a[N];
int lg[1<<23],cnt[1<<23];
int f[1<<23],g[M][1<<22],c[M][M];

int main() {
    n=read(),m=read(),k=read();
    for (int i=1;i<=n;++i) a[i]=read()-1;
    for (int i=2;i<=n;++i) ++c[a[i-1]][a[i]];
    for (int i=2;i<1<<m;++i) lg[i]=lg[i>>1]+1;
    for (int i=1;i<1<<m;++i) cnt[i]=cnt[i^(i&-i)]+1;
    for (int i=0;i<m;++i) {
        for (int j=0;j<m;++j)
            if (i!=j) g[i][0]+=k*c[j][i]-c[i][j];
        for (int S=1;S<1<<(m-1);++S) {
            int p=lg[S&-S]; if (p>=i) ++p;
            g[i][S]=(g[i][S^(S&-S)]+c[i][p]*(1+k)+c[p][i]*(1-k));
        }
    }
    memset(f,0x3f,sizeof(f)); f[0]=0;
    for (int S=1;S<1<<m;++S) {
        for (int i=0;i<m;++i) {
            if (!(S&(1<<i))) continue;
            int T=S^(1<<i);
            f[S]=min(f[S],f[T]+cnt[S]*g[i][(T&((1<<i)-1))|(T>>(i+1)<<i)]);
        }
    }
    printf("%d\n",f[(1<<m)-1]);
    return 0;
}