题意:
给定字符串序列({s_i}_{i=1}^n),对于每个字符串删除其中至多一个字符,使得字符串序列变成字典序(非严格)递增序列,求方案数.
其中两种方案不同当且仅当存在至少一个字符串在两个方案中删除的位置不同,或者在一个方案中删除而在另一个方案中没有删除.
题解:
为了方便,对每个字符串后增加一个'#'('#'比字母的ASCII码都要小),问题就变成对每个字符串删除其中恰好一个字符.
容易考虑到DP状态:记(dp[i,j])表示子问题({s_k}_{k=1}^i)在第(i)个字符串删除第(j)个(从(0)开始)位置时的答案.
使用(t_{i,j})表示(s_i)在去掉第(j)个字符时对应的字符串,那么容易写出状态转移方程:
为了方便,在最前面增加一个字符串"#",并初始化状态为(dp[0,0]=1).最终答案为(sum_{0le i<|s_n|}dp[n,i]).
显然总状态数是(displaystylesum_{i=1}^n|s_n|).
如果能将所有({t_{i,j}}_{0le jle|s_i|-1},{t_{i-1,j}}_{0le jle|s_{i-1}|-1})排序,那么可以统计前缀和从而做到(O(|s_{i-1}|+|s_i|))相邻两层转移.
如果能够(O(1))比较两个(t)的大小,就可以在(O((|s_{i-1}|+|s_i|)log(|s_{i-1}|+|s_i|)))时间内完成排序.
考虑两个(可能相同)字符串(p,q),为了方便令(|p|=|q|),使用(p'_i)表示(p)去掉第(i)个位置的字符串,(pI)表示(p)由区间(I)对应下标组成的子串.
现在要比较(p'_i)和(q'_j)的大小.记(x=min(i,j),y=max(i,j)).
如果(p[0,x)
e q[0,x)),那么可以直接比较大小;否则:
- 如果(i=j),那么可以直接比较(p[y+1,|p|))和q([y+1,|q|))的大小.
- 如果(i<j),那么需要先比较(p[i+1,j])和(q[i,j))的大小,再比较(p[y+1,|p|))和(q[y+1,|q|))的大小.
- 如果(i>j),那么需要先比较(p[i,j))和(q[i+1,j])的大小,再比较(p[y+1,|p|))和(q[y+1,|q|))的大小.
可以发现比较时只会比较两个字符串下标至多不超过(1)的位置,预处理出所有({p_i-q_i},{p_i-q_{i+1}},{p_{i+1}-q_i}).
以及对于这三个序列,预处理从每个位置开始第一个非(0)位置,那么就可以(O(1))比较(p'_i)和(q'_j)的大小.
为了方便,在比较(t)的时候,可以分别预处理((s_{i-1},s_{i-1}),(s_{i-1},s_i),(s_i,s_{i-1}),(s_i,s_i))四对字符串.
由于(|s_i|)可能不等于(|s_{i-1}|),可以在较短的字符串后补齐'#'.如果(|s_i|)被补齐,那么完成这一层转移后需要去掉末尾多余的'#'(只留下一个'#').
最后考虑复杂度就会变成(O(sum_{i=1}^nmax(|s_i|,|s_{i-1}|)logmax(|s_i|,|s_{i-1}|))),实际上渐进等价于(O(sum_{i=1}^n|s_i|logsum_{i=1}^n|s_i|)).
代码