标签：do leftarrow Od times deski P8386 dp

P8386 [PA2021] Od deski do deski

洛谷：Od deski do deski

LOJ3600 Od deski do deski

Solution

先考虑如何判定一个序列 \(a\) 是否合法。

记 \(dp_{i} = 0/1\) 表示考虑前 \(i\) 个数是否能被删空：\(dp_{i} \xleftarrow{\texttt{or}} dp_{j - 1}[a_i = a_j]\)。初始化 \(dp_{0} = 1\)。

类似地把判定性问题转成计数问题。

从前往后填数，由于合法状态与非法状态之间可以相互转化，所以我们要同时记录这两种情况的数量。

填数时要考察当前填多少个数合/非法，因此要记录这样一个信息：之前有多少不同的数值 \(x\)，使得存在 \(dp_{j - 1} = 1\) 且 \(a_j = x\)。

记 \(f_{i, j}\) 表示填完前 \(i\) 个数，所有 \(dp_{p - 1} = 1(p < i)\) 对应的 \(a_p\) 组成的数集大小为 \(j\) 的合法方案数，\(g_{i, j}\) 表示同样意义下的非法方案数。

\[\begin{aligned} f_{i, j} &\leftarrow j \times f_{i - 1, j} \\ f_{i, j} &\leftarrow j \times g_{i - 1, j} \\ g_{i, j} &\leftarrow (m - j) \times g_{i - 1, j} \\ g_{i, j + 1} &\leftarrow (m - j) \times f_{i - 1, j} \\ \end{aligned} \]

由于最后一个转移是由合法状态转移过来，并且当前位置上填了新的数值，因此数集的大小加一。

时间复杂度 \(O(n\times \min(n, m))\)。

code

标签：do,leftarrow,Od,times,deski,P8386,dp
From： https://www.cnblogs.com/Schucking-Sattin/p/17675461.html