2014-2015 Petrozavodsk Winter Training Camp, Contest.58 (Makoto rng_58 Soejima contest)

B - Dictionary

题目大意：

给出\(1\le n\le50\)个只有小写英文字母和?组成的字符串\(s_1,\cdots,s_n\)，\(1\le|s_i|\le20\).

求有多少种方案，将所有?换成小写英文字母，并且满足\(s_1<s_2<\cdots<s_n\).

题解：

首先通过给长度不够的字符串末尾添加同一个字典序小于’a’的字符的方式将所有串的长度统一，设这个长度为\(m\)。

这样，如果两个串\(s_i\)与\(s_j\)长度为\(k\)的后缀已经决定了大小关系，则它们除去该后缀之外的两个前缀应该完全相同。

这样我们可以考虑从后往前进行dp，从后往前为每个字符串填上小写字母。

令\(f[len][l][r]\)表示\(s_l,\cdots,s_r\)通过后缀\(s[len\cdots m]\)确定了\(s_l<s_{l+1}<\cdots<s_r\)的大小关系的方案数，则有递归基\(f[m+1][i][i]=1\).

这样我们就可以横向地进行dp，而纵向的部分需要另一个dp来辅助。

假设我们当前正在做\(f[len][l][r]\)的dp，令\(g[i][x]\)表示\(s_l,\cdots,s_i\)可以确定大小关系，且\(s_i\)当前位置填的字符为\(x\)的方案数。

则有递归基\(g[l-1][x]=1\)，

转移方法为，枚举\(s_r\)当前位可以填的字符\(k\)，再枚举\(i\)满足\(s_i,\cdots,s_r\)都可以填字符\(k\)，则有\(\displaystyle g[r][k]=\sum_i\sum_{j<k}g[i-1][j]\times f[len+1][i][r]\)。

做完\(g\)之后，当前位置的\(f\)也得到了：\(f[len][l][r]=\sum_k g[r][k]\).

通过处理\(g\)的前缀和，算法总的时间复杂度为\(O(n^2m\sigma)\)，空间复杂度为\(O(n^2m+n\sigma)\)，\(\sigma\)为字符集大小。