3579.晚安。
2026-07-23
题解
对于这道题,由于状态并不好计算,考虑一个朴素的 DP:f[k][i][j] 表示将 a[i] 和 a[j] 进行匹配,目前进行到第 k 位的价值。
显然,转移是简单的:f[k][i][j]=f[k−1][i][j]+C(g[a[i]][k],g[a[j]][k]),其中 C(i,j) 表示二进制对应位置为 i,j 所能得到的价值。
这个状态空间太大,怎么办?这时候要用到:
高低位拆分
注意到 DP 转移中,各位相互独立,并且值域很小,a[i]∈[0,220),所以,我们不妨把 a[i] 塞进状态里,怎么塞?具体的,我们设最大的 a 有 K 位,那么令 H+L=K,显然,在 H 接近 L 时,2H,2L 与 V 同阶。
接下来我们把 x 拆成 (A,B),其中 A 是前 H 位,B 是后 L 位。
由于价值函数相互独立,考虑把 cost(x,y) 拆成 costH(A,C)+costL(B,D),其中 x=(A,B),y=(C,D)。
现在我们要最大化这个权值,容易观察到:costH 只与 A,C 有关,costL 只与 B,D 有关,也就是说我们可以固定 A,D 找最大的 B,C。
根据我们的观察,令 F[A][D] 表示所有高位为 A 的数,其 B 与 D 的 costL 的最大值(注意 A,D 为变量)。
同样的,我们定义 G[A][D] 用来找到最大的 C。
经过我们的神秘操作,现在的序列最大值就是 A,Dmax(F[A][D]+G[A][D])。
还记得前面分析的 2H,2L 与谁同阶么?没错,枚举 A,D 的复杂度为 O(V),现在我们知道怎么从 F,G 算出答案了。
那么怎么算 F,G 呢?考虑一个 DP:(用魔法击败魔法)
我们以求出 F 为例,设 f[k][S] 表示当前处理到第 k 位,且二进制压缩为 S,其中 S 会在 DP 过程中逐渐变化,可以理解为 B 与 D 的中转状态。
具体的,S 的前 K−k 位为未转移的 B,后 k 位为转移后的 D。
初始时,我们将当前 A 对应的所有 B 存入 f[0][B],然后开始枚举第 k 位为 0 或 1,并将 B 的第 k 位替换,放入 k+1 的对应状态中。
全部处理完毕后,我们将 f[k] 中所有元素复制到 F[A] 中即可,总共有 2H 种 A,每个 A 的预处理复杂度为 O(2L⋅L),总复杂度为 O(2H⋅2L⋅L)=O(VlogV),G 的处理相同。
