省选联考2020·信号传递

初步

对于 $S$ 的每一位向他的后一位连一条边，记 $g[u][v]$ 为 $u \to v$ 连边的边数。

然后考虑每一条边 $u\to v$ 对答案的贡献，记 $pos_u$ 为给 $u$ 安排的位置

$$w(u,v)= \{ \begin{aligned} &pos_v-pos_u &(pos_u<pos_v)\\ &k\times (pos_x+pos_y)&(pos_u>pos_v) \end{aligned}$$

显然，每一条边的每一个端点的贡献是独立的，所以我们可以对每个结点去考虑贡献，$m$ 又如此小，考虑状压

$dp[S]$ 表示选取的状态为 $S$ 的最小能耗

$$dp[S]=\min_{x\in S}\{ dp[S-x]+|S|\times \sum_{y\in S-x}g[y][x]+k\times g[x][y]+|S|\times \sum_{v\notin S}k\times g[y][x]-g[x][y]\}$$

结合上图和每条边的贡献，状态转移方程是不难理解的

优化时间

这样枚举状态，枚举 $x$ 枚举 $y$，时间复杂度是 $O(m^22^m)$ 的，无法接受。

考虑预处理出每个状态转移时的 $|S|$（即 $pos_x$）的系数。

设 $cost[x][S]$ 为 $dp[S]$ 向 $dp[S+x]$ 转移时的系数

$$\begin{aligned} cost[y][S+y]&=cost[y][S]+k\times g[x][y]+g[y][x]-k\times g[y][x]+g[x][y]\\ &=(1+k)\times g[x][y]+(1-k)\times g[y][x] \end{aligned}$$

简单解释一下：因为 $x$ 新加入了 $S$ 集合，加上 $x$ 在集合 $S$ 中的贡献，再刨去之前算的 $x$ 不在集合 $S$ 中的贡献

这样时间复杂度降为 $O(m2^m)$ ，在时间方面可以通过此题。

优化空间

A：$m\le 23$ ，你 $cost$ 数组开多大？

B：$emm...$ ，$\frac{2^{23}\times 23\times 2}{1024*1024}=736$ ，空间限制 $512MB$，……

A：有冗余状态🐴？

B：em……，对于 $x\in S$，$cost[x][S]$ 是冗余的，哦！那可以直接枚举一个二进制长度为 $m-1$ 的长度，表示不算 $x$ 时选的结点，……哦可能这么说你不太懂，那直接看代码吧

1
2
3
4
5
6
7
8
9
10
11
12

for (int i = 0; i < m; ++i) {//枚举不算的那个点
    for (int j = 0; j < m; ++j)
        if (i != j)
            cost[i][0] += k * E[j][i] - E[i][j];//初始化
    for (int S = 1; S < 1 << (m - 1); ++S) {
        int x = lg[(S & -S)];
        if (x >= i)
            ++x;
        //因为我刨除了i，所以要把i那一位腾出来
        cost[i][S] = (cost[i][S ^ (S & -S)] + E[i][x] * (1 + k) + E[x][i] * (1 - k));
    }
}

A：现在空间够了吧？

B：对，$cost$ 只需要开 $\frac{2^{22}\times 23\times 2}{1024*1024}=368$

A：还有其他细节吗

B：哦……，你对 $f$ 进行转移的时候要把状态还原到 $cost$ 的状态上，看下代码：

1

f[S]=min(f[S],f[_S]+sz[S]*cost[i][(_S>>(i+1)<<i)|(_S&((1<<i)-1))]);