原题链接

思路

手搓样例，发现用分裂根本不符合人类认知规律，遂使用合并。一秒想到区间 dp，用 $d{p}_{i,j}$ 表示 $i,j$ 之间的字母合并后可以得到多长的只包含“S”的字符串（记录最短长度）。可是要是先把 $i,k$ 之间的合并得到“A”，再把 $k+1,j$ 之间的合并得到“B”，最后把“A”和“B”合并得到“S”，该怎么表示？
首先，当一段字母合并后得到了一个不是“S”的字母时，就必须要再和左右两边的字母合并，最终得到“S”。其次，如果得到了“S”，就可以选择继续合并或者把几个合并得到的“S”拼起来（我们默认初始的每个字母是由这个字母本身合并得到的）。所以可以先用 $m{g}_{i,j}$ 进行 $\lceil$ 合并成一个字母 $\rfloor$ 的操作，然后用 $d{p}_{i,j}$ 进一步实现 $\lceil$ 把几个“S”拼起来 $\rfloor$ 的操作。
由于合并得到的是单个字母，可以用状态压缩进行表示，$m{g}_{i,j}$ 在二进制下从低到高第 $k$ 位如果是 $1$，表示可以用 $i,j$ 之间的字母合并得到char('A'+k)。$dp$ 和 $mg$ 都采取枚举断点 $k$ 的方法计算。$d{p}_{i,j}$ 的边界情况是：

1. $i=j$ 时，若 $s_i$ 是“S”，那么 $d{p}_{i,j}=1$，否则是 INF。
2. $i<j$ 时，若 $i,j$ 之间的字母可以合并得到一个“S”，即mg[i][j]&(1<<'S'-'A')，那么 $d{p}_{i,j}=1$。

代码

#include<bits/stdc++.h>
using namespace std;
int can[26][26],n,kk;
int dp[105][105],mg[105][105];
string s;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>s;can[s[1]-'A'][s[2]-'A']|=1<<s[0]-'A';}cin>>kk;for(int i=1;i<=kk;i++){cin>>s;int si=s.size();s=' '+s;memset(mg,0,sizeof(mg));for(int l=1;l<=si;l++) mg[l][l]=1<<s[l]-'A';for(int j=2;j<=si;j++)for(int l=1;l+j-1<=si;l++){int k=l+j-1;for(int mid=l;mid<k;mid++)for(int a=0;a<26;a++)if(mg[l][mid]&(1<<a))for(int b=0;b<26;b++)if(mg[mid+1][k]&(1<<b))mg[l][k]|=can[a][b];}memset(dp,0x3f,sizeof(dp));for(int j=1;j<=si;j++)for(int l=1;l+j-1<=si;l++){int k=l+j-1;if(mg[l][k]&(1<<'S'-'A')){dp[l][k]=1;continue;}for(int mid=l;mid<k;mid++)dp[l][k]=min(dp[l][k],dp[l][mid]+dp[mid+1][k]);}if(dp[1][si]<0x3f3f3f3f) cout<<dp[1][si]<<endl;else cout<<"NIE\n";}return 0;
}