亲眼目睹卡常成为OI考点之一……（不带你这么玩的 :(）
# 题面
> 洛谷 P6622
点击展开/折叠题面
一条道路上从左至右排列着 $m$ 个信号站，初始时从左至右依次编号为 $1,2,\dots,m$，相邻信号站之间相隔 $1$ 单位长度。每个信号站只能往它右侧的任意信号站传输信号（称为普通传递），每单位长度距离需要消耗 $1$ 单位时间。道路的最左侧有一个控制塔，它在最左侧信号站的左侧，与其相隔 $1$ 单位长度。控制塔能与任意信号站进行双向信号传递（称为特殊传递），但每单位长度距离需要消耗 $k$ 个单位时间。对于给定的长度为 $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}$，则信号无须传递。
阿基作为大工程师，他能够任意多次交换任意两个信号站的位置，即他能够重排信号站的顺序，这样会使得 $S$ 消耗的传递时间改变。现在阿基想知道，在他重排信号站顺序后，$S$ 所消耗的传递时间最小能是多少。
# 解析
注意到 $m$ 非常小，很容易想到状压。
先做一步简单的优化：因为我们发现两个信号塔之间的传递，其实不分先后，只分次数；也就是说可以只储存 $next_{i,j}$ 表示从信号塔 $i$ 传输到信号塔 $j$ 的次数。
于是考虑从左往右确定每个位置是多少号信号塔，并记已经确定位置的信号塔集合 为 $S$。我们发现，信号塔 $i$ 的贡献只取决于哪些信号塔在它前面（剩下的就在它后面），于是我们可以直接用 $S$ 计算出确定下一个位置为信号塔 $i$ 产生的新的代价。
为了表述方便，下文用 $p_i$ 表示信号塔 $i$ 的位置。
记 $f_S$ 表示当前已经确定了位置（从左到右）的信号塔的集合为 $S$，最小代价是多少。可以推得转移：
假设从 $T$ 转移到 $S$，即 $T+\{i\}=S$，那么 $p_i=|T|+1$。则考虑 $i$ 的新增代价：
- 从另一信号塔 $j$ 到 $i$ 的传输：
- 如果 $j\in T$，则 $j$ 在 $i$ 前面，则代价为 $(p_i-p_j)$，只看 $i$ 的代价则是 $+p_i$；
- 如果 $j\not\in T$，则 $j$ 在 $i$ 后面，代价为 $k(p_i+p_j)$，则 $i$ 的代价是 $+kp_i$；
- 从信号塔 $i$ 到 $j$ 的传输：
- 如果 $j\in T$，则代价为 $k(p_i+p_j)$，则 $i$ 的代价为 $+kp_i$；
- 如果 $j\not\in T$，则代价为 $(p_j-p_i)$，则 $i$ 的代价为 $-p_i$；
综上，可以得到转移式：
此时复杂度为 $O(m^22^m)$，显然不能通过，我们发现枚举下一个信号塔 $i$ 必不可少，那么可能减少的只有枚举 $j$。
我们发现对于固定的 $i,T$，下面的值是固定的：
于是可以预处理这些值，具体的话可以递推：利用 $T’+\{t\}=T$ 的 $g_{i,T’}$ 来增加一个 $t$ 进入集合，计算额外代价从而得到 $g_{i,T}$。复杂度 $O(m2^m)$，而转移式又可以写成：
复杂度也是 $O(m2^m)$。
现在时空复杂度都是 $O(m2^m)$ 了。但是空间开不下……（指 $g$ 数组）
然后 tly dalao 就讲了一个巧妙操作 :) 把 $T$ 从中间分成两部分，即 $T=T_0+T_1$，其中 $|T_0|=|T_1|=\frac m2$。然后就可以再把 $g$ 数组拆开，比如：
其他的类似，然后我们就不储存 $g$，而是储存 $h$——空间复杂度就优化到了 $O(2^{m/2}m)$~
# 源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=23,HM=12;
inline int Ri(){
register int a=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
return a;
}
int n,m,co;
int A[N],nxt[M][M];
int f[1<<M],g[1<<HM][M][8],lg2[1<<M],siz[1<<M];
#define lowbit(x) ((x)&(-(x)))
int main(){
n=Ri(),m=Ri(),co=Ri();
for(register int i=1;i<=n;i++) A[i]=Ri()-1;
for(register int i=2;i<=n;i++)
if(A[i-1]!=A[i])
nxt[A[i-1]][A[i]]++;
int haf=m>>1,all0=(1<<haf)-1,all1=(1<<(m-haf))-1,all=(1<<m)-1;
for(register int i=0;i<m;i++) lg2[1<<i]=i;
for(register int i=0;i<m;i++)
for(register int j=0;j<haf;j++)
g[0][i][2]+=nxt[i][j],g[0][i][6]+=nxt[j][i];
for(register int S=1;S<=all0;S++){
int las=lowbit(S),j=lg2[las],T=S^las;
for(register int i=0;i<m;i++){
g[S][i][0]=g[T][i][0]+nxt[i][j];
g[S][i][2]=g[T][i][2]-nxt[i][j];
g[S][i][4]=g[T][i][4]+nxt[j][i];
g[S][i][6]=g[T][i][6]-nxt[j][i];
}
}
for(register int i=0;i<m;i++)
for(register int j=haf;j<m;j++)
g[0][i][3]+=nxt[i][j],g[0][i][7]+=nxt[j][i];
for(register int S=1;S<=all1;S++){
int las=lowbit(S),j=haf+lg2[las],T=S^las;
for(register int i=0;i<m;i++){
g[S][i][1]=g[T][i][1]+nxt[i][j];
g[S][i][3]=g[T][i][3]-nxt[i][j];
g[S][i][5]=g[T][i][5]+nxt[j][i];
g[S][i][7]=g[T][i][7]-nxt[j][i];
}
}
memset(f,0x3f,sizeof f);f[0]=0;
for(register int T=0;T<all;T++){
if(T) siz[T]=siz[T^lowbit(T)]+1;
int mul=siz[T]+1;
int T0=T&all0,T1=T>>haf;
for(register int i=0;i<m;i++)
if(!(T>>i&1)){
int add=co*(g[T0][i][0]+g[T0][i][6])+g[T0][i][4]-g[T0][i][2]+
co*(g[T1][i][1]+g[T1][i][7])+g[T1][i][5]-g[T1][i][3];
f[T|(1<<i)]=min(f[T|(1<<i)],f[T]+mul*add);
}
}
printf("%d\n",f[all]);
return 0;
}
|
THE END
Thanks for reading!