标签：数列 T3 注意 LIS rm 考虑 CW dp

前言

老登你也知道你又在出 \(\rm{LIS}\)

算法

首先我们需要注意到, 本质上和随机了一个 \(1 \sim n\) 的排列没有任何区别
具体的, 任意一个 \(\rm{LIS}\) 数列, 都仅仅是由大小关系推过来的, 并且可以证明, \(\rm{LIS}\) 数列相同, 当且仅当大小关系完全相同

注意到这个之后(事实上我注意不到) , 我们可以拿到暴力的 \(20\%\)

先考虑全是 \(0\) 的情况
注意到 \(\rm{LIS}\) 的数列, 必须满足

\[a_1 = 1, a_i \leq \mathop{ \rm{max} }\limits_{j < i} (a_j + 1), a_i \geq 1 \]

用 \(dp_{i, j}\) 表示考虑了前 \(i\) 位, 其中 \(\mathop{ \rm{max} }\limits_{k < i} (a_k) = j\) 时可能性数量
转移是显然的 (注意最大值一次只能变化 \(1\))

\[dp_{i, j} = j dp_{i - 1, j} + dp_{i - 1, j - 1} \]

考虑 \(a_i\) 被指定的情况
有,

\[dp_{i, j} = dp_{i - 1, j} , j > a_i \]

\[dp_{i, a_i} = dp_{i - 1, a_i - 1} + dp_{i - 1, a_i} \]

现在我们需要考虑 \(a_i = -1\) 的情况
由于这一位不受关注, 我们直接填上最大的可能, 即

\[dp_{i, j} = dp_{i - 1, j - 1} \]

具体的, 只要填上最大的数, 后面所有的可能都可以被考虑到

时间复杂度 \(\mathcal{O}(n ^ 2)\)

代码

略

总结

一般来说, 可以将约束条件加入 \(\rm{dp}\) 柿子方便递推

这个题中, 关键信息是 : 最大值一次变化量最大为 \(1\)

积累一下, 思路确实非常好, 善于利用 \(\rm{Subtask}\) 推到正解

还是需要多联系 \(\rm{dp}\)

标签：数列,T3,注意,LIS,rm,考虑,CW,dp
From： https://www.cnblogs.com/YzaCsp/p/18558657