Description
一条道路上从左至右排列着 $m$ 个信号站，初始时从左至右依次编号为 $1,2,dots,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$ 所消耗的传递时间最小能是多少。
Solution
将$i-j$和$K(i+j)$中$i$和$j$的贡献拆开放到每个信号站
设$f_{S}$表示从左往右排列了$S$中的所有信号站的最小花费，$g_{i,S}$表示$i$信号站前方的点集为$S$时$i$做的贡献
$$f_{S}+g_{i,S} ightarrow f_{S+i}$$
因为不需要维护$S$中包含$i$的g_{i,S}，时间复杂度$O(m2^{m-1})$
#include<iostream> #include<cstdio> using namespace std; int n,m,K,las,now,mp[23][23],g[23][4200005],lg[8500005],siz[8500005],dp[8500005]; inline int read(){ int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } int main(){ n=read(),m=read(),K=read(),lg[0]=-1; for(int i=1;i<=n;i++){ now=read()-1; if(i>1)++mp[las][now]; las=now; } for(int i=1;i<(1<<m);i++)lg[i]=lg[i>>1]+1,siz[i]=siz[i>>1]+(i&1); for(int i=0;i<m;i++){ for(int j=0;j<m;j++)if(i!=j)g[i][0]+=mp[j][i]*K-mp[i][j]; for(int j=1;j<(1<<(m-1));j++){ int y=j&-j,z=lg[y]; z+=(z>=i),g[i][j]=g[i][j^y]+mp[i][z]*(1+K)+mp[z][i]*(1-K); } } for(int i=1;i<(1<<m);i++){ dp[i]=0x7f7f7f7f; for(int x=i,y;y=x&-x;x^=y){ int z=lg[y],w=i^y; dp[i]=min(dp[i],dp[w]+g[z][w&y-1|w>>z+1<<z]*siz[i]); } } printf("%d ",dp[(1<<m)-1]); return 0; }