给定的长度为 \(n\) 的信号传递序列 \(S\)，有传递规则：
-
共 \(n-1\) 次信号传递，第 \(i\) 次信号传递将把信号从 \(S_i\) 号信号站传递给 \(S_{i+1}\) 号。
-
若 \(S_{i+1}\) 号信号站在 \(S_i\) 号右侧，则将使用普通传递方式，从 \(S_i\) 号直接传递给 \(S_{i+1}\) 号。
-
若 \(S_{i+1}\) 号信号站在 \(S_i\) 号左侧，则将使用特殊传递方式，信号将从 \(S_i\) 号传递给控制塔，再由控制塔传递给 \(S_{i+1}\) 号。
-
若 \(S_i=S_{i+1}\)，则信号无须传递。
特殊传递耗时 \(k\) 秒/距离，普通传递耗时1秒/距离，有 \(m\) 个站点，求所有排列中最小时间和。
\(2\leq m\leq 23\)，\(2\leq n\leq 10^5\)，\(1\leq k\leq 100\)，\(1\leq S_i\leq m\)。
是道好题，但卡常。
这里给出一个卡满时空的暴力做法。首先是 \(2^m\times m^2\) 的做法，用 \(dp[S]\) 表示在前 \(|S|\) 个位置上填上 \(S\) 这些数得到的最短时间消耗，然后每一次更新枚举一个新的点 \(i\) ，并枚举所有点计算贡献，空间 \(O(2^m)\) 时间 $ O(2^m\times m^2)$ ,TLE。
然后考虑用空间换时间，可以想到先预处理出 \(pre[S][i]\) 表示在 \(S\) 状态下加上 \(i\) 所产生的贡献，这可以从 \(pre[S-j][i]\) 上转移过来。但 \(O(m\times 2^m)\) 正好爆空间，所以只能预处理出约 \(510MB\) 的信息，剩下没有处理的暴力计算，正好 \(510.62MB\,\,\,2.80ms\) 卡过。
#include<bits/stdc++.h>
using namespace std;
#define maxS 1<<23
#define maxs 5208333
int n,m,K,a[100005];
int pre[maxs][24];
int dp[maxS],now;
int cnt[30][30],ans[30][30];
int h[30];
map<int,int> M;
int count(int x){
int cnt=0;
while(x){
x-=x&(-x);
cnt++;
}
return cnt;
}
int main(){
scanf("%d %d %d",&n,&m,&K);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(i!=1)
cnt[a[i-1]][a[i]]++;
}
for(int j=1;j<=m;++j){
for(int k=1;k<=m;++k){
if(j!=k)
pre[0][j]+=-cnt[j][k]+K*cnt[k][j];
ans[j][k]=(K*cnt[j][k]+cnt[k][j])-(-cnt[j][k]+K*cnt[k][j]);
}
}
for(int i=1;i<=m;++i){
M[1<<(i-1)]=i;
h[i]=1<<(i-1);
}
int S=(1<<m)-1;
for(int i=1;i<=min(S,maxs);++i){
for(int j=1;j<=m;++j){
if(!(i&h[j])){
int k=M[i&(-i)];
pre[i][j]=pre[i^h[k]][j]+ans[j][k];
}
}
}
for(int i=1;i<=S;++i)
dp[i]=1000000000;
dp[0]=0;
for(int i=0;i<=S;++i){
int pos=count(i)+1;
for(int j=1;j<=m;++j){
if(!(i&(1<<(j-1)))){
if(i<=min(S,maxs))
dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+pos*pre[i][j]);
else{
now=dp[i];
for(int k=1;k<=m;++k){
if(k==j)
continue;
if(!(i&(1<<(k-1)))){
now+=pos*(-cnt[j][k]+K*cnt[k][j]);
}
else{
now+=pos*(K*cnt[j][k]+cnt[k][j]);
}
}
dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],now);
}
}
}
}
printf("%d\n",dp[S]);
return 0;
}