ABC450G题解是什么？

本做法为随机化做法，思路是这篇题解 题目链接 记选的 \(6\) 个题目为 \(k_{1/2/3/4/5/6}\)。 首先我们将题目类型随机赋值为 \(0/1/2/3\)，显然原来不合法的方案在随机赋值之后仍然不合法，而实际上的最优解在现在仍然合法的概率为 $\frac{3}{256} $。 证明： \(k_3\) 与 \(k_4\) 不相同的概率为 \(\frac{3}{4}\)，因为 \(k_3\) 可以随便取，之后 \(k_4\) 的值只能在 \(0/1/2/3\) 中挑除了 \(k_3\) 以外剩下的 \(3\) 个。 固定 \(k_3\) 与 \(k_4\) 之后，\(k_{1/2/3/4}\) 互不相同的概率为 \(\frac{1}{4} \times \frac{2}{4}=\frac{1}{8}\)，因为 \(k_1\) 可以挑 \(4\) 个中的 \(2\) 个，\(k_2\) 只能挑 \(4\) 个中的 \(1\) 个。 同理 \(k_{3/4/5/6}\) 互不相同的概率也为 \(\frac{1}{8}\)。总概率为 \(\frac{3}{4} \times \frac{1}{8}\times \frac{1}{8}=\frac{3}{256}\)。 这样我们就将题目类型数缩减到了 \(4\)。设随机赋值后新的题目类型为 \(g_i\)。 接下来我们维护以下信息 \[pre_{i,j}= \max\limits_{1\le k \le i \bigwedge g_k=j}a_k \] \[suf_{i,j}= \max\limits_{i\le k \le n \bigwedge g_k=j}a_k \] \[s_{i,j} = a_i+\sum_{k\in \left \{ 0,1,2,3 \right \} \bigwedge k \ne g_i \bigwedge k \ne j}suf_{i+1,k} \] \[t_{i,j,k} = \max\limits_{i \le sufi \le n \bigwedge g_{sufi} = j} s_{sufi,k} \] 我们枚举第三个题目的位置 \(i\)，与第四个题目的类型 \(j\)。 那么此时的答案为 \[a_i + t_{i+1,j,g_i} + \sum_{k\in \left \{ 0,1,2,3 \right \} \bigwedge k \ne g_i \bigwedge k \ne j} pre_{i-1,k} \] 这样我们以 \(O(n)\) 的时间复杂度解决了问题。 接着我们随机赋值 \(600\) 次，那么错误率为 \((1-\frac{3}{256})^{600} \approx 8 \times 10^{-4}\)。可以接受。 实测 \(T = 300\) 时 WA 两个点， \(T = 500\) 时可以通过。