传送门
题意：给定一个长度为 \(n\)，包含
+和-的字符串 \(s\)。求长度等于 \(n\) 的排列 \(p\) 的数量，满足对于所有 \(1 \le i \le n\)，若 \(s_i=\)+，则 \(p_i > i\)。
数据范围不明确。经测试，要求单组时间复杂度在 \(O(n^2)\) 左右。
这里对排列中填数的限制，既有“前缀”又有“后缀”限制。不是特别好 DP。
这里一种较为清晰的思考方式是，我如果依次将 \(1,2,\dots,n\) 填入序列，有多少种方案。
然后结合前缀的 DP 状态设计，设 \(f_i\) 表示考虑前缀 \(i\) 个字符的限制，枚举到 \(i\) 就要决定 \(i\) 该填到哪里去。然后发现无法确定 \(i\) 填到当前下标的前面还是后面，也无法确定 \(p_i\) 该填什么数。
考虑对于一个值 \(i\)，如果它填到的位置 \(j>i\)，那么我们在 DP 到 \(i\) 的时候先不填 \(i\)，等到 DP 到 \(j\) 的时候再考虑 \(i\) 的填入。
于是可以设，\(f_{i,j}\) 表示考虑前缀 \(i\)，同时 \(s_1\sim s_i\) 有 \(j\) 个加号是在当时没有填入数字，要延迟填入。
注意这里只有加号可以进行延迟考虑的操作，如果 \(s_i\) 为加号，那么在 DP 的过程中，一定要决定 \(p_i\) 填什么。
分类考虑：
-
若 \(s_i\) 是减号：
我们考虑 \(i\) 何去何从。一种方案是，前面不是空了 \(j\) 个数延迟填入吗，他们一定都是小于 \(i\) 的。那么我们可以从这 \(j\) 个数中选一个填入 \(p_i\)，而 \(i\) 这个数丢到后面再填。则 \(f_{i,j} \gets f_{i-1,j} \times j\)。
另一种方案是，\(i\) 可以填入所有的前面丢下的空位中的任意一个，所以让 \(i\) 选一个填入就行。但是由于状态的定义，我们对于第 \(i\) 个位置一定要从前面延迟填入的数中，拿过来一个填进 \(p_i\)。这样填，空位会减少一个。前 \(i-1\) 的前缀中，有 \(j+1\) 个空位。故 \(f_{i,j} \gets f_{i-1,j+1} \times (j+1)^2\)。 -
若 \(s_i\) 是加号：
\(i\) 往前填，空位数不变。\(i\) 延迟填入，空位数相比于 \(i-1\) 会增加 \(1\)。故 \(f_{i,j}=f_{i-1, j}\times j + f_{i-1, j-1}\)。
时间复杂度 \(O(n^2)\)，注意多测清空。代码非常好写，略。