小清新区间动态规划

EnofTaiPeople · 2023-03-05 10:12:35 · 题解

Part1 前言

题意：给定 n 个 m 位数 a_i，有 ? 表示该位不确定，我们需要求出将每一个 ? 转换成 0\sim9 使得 a_i<a_{i+1} 的方案数，n,m\le40。

要是 m\le7 就好了！不过怎么可能？

当然如果每个数字的 ? 都不超过 7 也好啊！然而也不可能。

当然这道题还是小清新的。

Part2 设计状态

考虑最高位的分布，首先一定不能存在逆序对。

我们可以简单认为是一段 1，一段 2，一直到一段 9，对于一段内的数字并没有得到严格偏序关系，所以我们需要它们在更低的位中得到严格偏序。

所以有很容易的想到了区间动态规划的形式：设 f_{i,l,r} 表示考虑了第 i 及以后的位数，区间 [l,r] 达成严格偏序的方案数。

边界是 f_{m,l,l}=\begin{cases}1,S_{l,m}\ne?\\10,S_{l,m}=?\end{cases}，f_{1,1,n} 是答案。

我们需要从 f_{i+1,l,r} 转移到 f_{i,l,r}，分两种情况。

1. 区间 [l,r] 在第 i 位完全相等，那么之前就一定要保证严格偏序，从 f_{i+1,l,r} 转移过来，需要考虑出现的非问号数字个数。

2. 区间 [l,r] 在第 i 位不完全相等，可以枚举最后一个完全相等区间。

Part3 具体实现

想到这里其实已经不难了，不过状态是真的神秘，这里我设 h_{L,R,l,r} 表示区间 [l,r] 该位为 [L,R] 形成严格偏序的方案数，然后就能 h_{L,R,l,r}\leftarrow h_{L,R',l,k}h_{R,R,k+1,r}，其中 R'<R，k 在 [l,r) 之间。

使用了前缀和优化，时间复杂度为 O(c^2mn^3)，但是跑不满，所以飞快，空间 O(c^2n^2)，其中 c 为数字值域，本题 c=10。

跟同学把这场写完之后，他告诉我这道题其实只需要记该位数字的最大值，但需要再开一维表示只使用某一个数字的答案，这样的时间复杂度为 O(cmn^3)，空间 O(cn^2)，实际上效率差不多。