Dictionary | Gym 100958B

题目链接

\(n\)小写字母和 ? 组成的字符串,问有多少种替换 ? 的方案,使得最终的字符串 \(S_1,S_2,\cdots,S_n\) 满足字典序递增。

\(n \le 50, |S_i| \le 20\)

我的解法:

在每个字符串的第一个字符被确定后发现第一个字符不同的串之间字典是关系已经确定,关系还未确定的(第一个字符相同)的串组成若干区间。

由于区间之间是独立的,将删掉所有串第一个字符后所有区间内部的合法方案数乘起来就是总方案数,而“删掉所有串第一个字符后所有区间内部的合法方案”是一个数量不多的子问题,考虑把“前多少个字符已经删掉”和“区间”作为 DP 的状态。

我们有一个状态的定义:\(f_{i,l,r}\) 表示只从每个串的第 \(i\) 个字符开始考虑,替换第 \(l\) 个到 \(r\) 个串中的 ? ,使得 \(S_l,S_{l+1},\cdots,S_r\) 满足字典序递增的方案数。

然后发现这个状态虽然描述清楚了子问题,但没有很显然的转移。为了实现高效的转移,每次转移时还需要做一个横向 DP,有点麻烦。

所有给这个状态在添加一维 \(k\) 表示第 \(l\) 个到 \(r\) 个串中第 \(i\) 个字符都必须大于等于 \(k\),然后就有很简单的递推:

枚举最小的 \(j \in [l,r]\),使得 \(S_{j}[i] > k\),也就是说 \(\forall x \in [l,j-1]\),有 \(S_x[i] = k\)\(\forall x \in [j,r]\),有 \(S_x[i] \ge k + 1\)\[ f_{i,l,r,k}=\sum\limits_{j=l}^{r+1}f_{i+1,l,j-1,'a'}\cdot f_{i,j,r,k+1} \] 为了处理较短的串提前结束而出现空字符的问题,记 \(k=-1\) 表示允许空字符出现。如果 \(S_l[i]\) 是空字符,那么它就等于 \(f_{i,l+1,r,'a'}\),否则是 \(f_{i,l,r,'a'}\),如果 \(k \ne -1\),那么 \(S_l[i]\) 就不能是空字符。

最后是边界条件:当 \(l > r\) 时值为 \(1\),当 \(l \le r \land k > 'z'\) 时值为 \(0\)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)

using namespace std;
const int P = 1e9 + 7;
typedef long long ll;
int n;
char S[55][25];
ll f[25][55][55][26];
ll dp(int i, int l, int r, int k) {
if(l > r) return 1; if(k > 25) return 0;
if(k == -1) return S[l][i] ? dp(i, l, r, 0) : dp(i, l + 1, r, 0);
if(!S[l][i]) return 0;
ll& res = f[i][l][r][k];
if(~res) return res; res = 0;
rep(j, l, r + 1) {
res = (res + dp(i + 1, l, j - 1, -1) * dp(i, j, r, k + 1)) % P;
if(S[j][i] != '?' && S[j][i] != 'a' + k) break;
}
return res;
}
int main() {
cin >> n;
rep(i, 1, n) cin >> (S[i] + 1);
mem(f, -1);
cout << dp(1, 1, n, 0);
return 0;
}
其他的解法:
  1. 第一篇代码状态设定和转移和我的解法相同,但对于空字符的处理是把它当做一个比“a"小的字符,然后将所有串的长度全部补成 \(20\),把 \(k='z'+1\)\(i=21\) 作为边界情况,同时限制 ? 不能变成空字符。但转移时需要特判没有字符 \(k\) 和全部是字符 \(k\) 的情况。

  2. 第二篇代码是把 \(f_{i,l,r}\) 作为状态,转移时作一个横向 DP,设 \(T_{i,j}\) 表示当前已经填了字符"a"-\(i\)(不一定用过),填好第 \(l\) 到第 \(i\) 个串的方案数。

    我不太清楚这样做的复杂度。

  3. 第三篇和第一篇的唯一区别是把空区间作为边界条件,转移时无需特判。