前言:为什么不放在题 1
因为题 \(1\) 收录的有点多了,现在编辑框都卡。预计加上 code 1300 行就要开新的了。
正文
AT_dp_t
如果设计状态为 \(f_{i,j}\) 表示考虑到前 \(i\) 个数第 \(i\) 个数为 \(j\) 的话将很难转移,因为这是排列,不能有重复。要是把前面的值都记下来就是暴力了。
什么东西不需要保证不重复呢又能转移呢?答案是排名,但是排名肯定不能重复吧?这里所说的是局部的排名,可以想象成动态的离散化,比如你先填了 \(1, 3, 5, 6\) 那排名为 \(1, 2, 3 ,4\),然后填了个 \(2\) 那排名就是 \(1, 3, 4, 5, 2\)。
考虑 \(f_{i, j}\) 表示前 \(i\) 个数最后一个数在这 \(i\) 个数中排名为 \(j\) 的方案数,这样的话就可以不考虑重复了。转移是显然的,前缀和优化即可。
有一个问题:为什么 \(f_{1, 1}\) 为 \(1\) 而不是 \(n\), 这是因为我们 dp 的过程中和值是无关的,最后得到的是一个全局的排名序列,显然这也是这个排列,比如最后排名为 \(5, 3, 2, 1, 4\) 那排列就是 \(5, 3, 2, 1, 4\), 所以只需要记录局部排名即可。
时间复杂度 \(\mathcal{O}(n^2)\)。