排列DP/线头DP

--待更新

满足性质

---

[AT-dp-t] Permutation

题目

有一个长为 $N$ 的正整数排列，给定一个由 < 和 > 组成的长为 $N-1$ 的的字符串。

对于任意满足 $1\le i\le N-1$ 的字符 $s_i$，如果 $s_i$ 是 < 则 $P_i<P_{i+1}$、如果 $s_i$ 是 > 则 $P_i>P_{i+1}$。

求满足这样的性质的排列 $P$ 的方案数。

Solution

先看数据范围 $n\le 3000$，可以用 $n^2$ 的算法去做，考虑使用排列dp。

先要知道一个比较重要的结论：

• 因为是排列，且题意只与相对的大小有关系，所以我们不需要关注每个数的具体的值。

设 $f_{i,j}$ 表示前 $i$ 个位置全部符合条件，且第 $i$ 个位置的值在前 $i$ 个值中排第 $j$ 小的方案数，这里就需要分类讨论：

• 1.对于 < 的情况，即 $p_{i-1}<p_i$，那么第 $i-1$ 个位置上的数排名必然比 $i$ 上的数字低，于是有：

$$f_{i,j}=\sum _{k=1}^{j-1}{f}_{i-1,k}$$

• 2.而对于 > 的情况，即 $p_{i-1}>p_i$，此时的第 $i-1$ 个数的排名肯定不会低于 $j$，且小于 $i-1$，（这里为什么可以是 $j$ 呢？因为第 $i-1$ 位的排名是基于前 $i-1$ 个数的，第 $i$ 个数插入进来不会影响），于是也有：

$$f_{i,j}=\sum _{k=j}^{i-1}{f}_{i-1,k}$$

会发现这里暴力转移的时间复杂度是 $O(n^3)$ 的，为了优化时间，我们可以用前缀和差分维护上一层的 $f$ 即可。

最终的答案就是 $Ans=\sum _{i=1}^n{f}_{n,i}$。

---

UVA1650 数字串 Number String

Solution

这题和上一题大同小异，就是多了一个未知的情况，那就代表 $p_{i-1}$ 有可能大于 $p_i$，也有可能是小于，将上面两种分类结合起来，就是：

$$f_{i,j}=\sum _{k=1}^{j-1}{f}_{i-1,k}+\sum _{k=j}^{i-1}{f}_{i-1,k}$$

将式子合并一下：

$$f_{i,j}=\sum _{k=1}^{i-1}{f}_{i-1,k}$$

---