原題鏈接

解析

首先可以想到區間 dp。

設 \(f_{l,r}\) 表示分裂出 \(T[l,r]\) 所需的最少 \(\texttt{S}\) 個數，其中 \(T\) 是目標串。

但是仔細思考后發現根本沒有辦法轉移，于是倒閉。

正難則反，考慮怎么合成。

設 \(f_{l,r}\) 表示合成 \(T[l,r]\) 中的字符后得到的最少 \(\texttt{S}\) 個數。

但是我們發現這個問題一點都不“子問題”，因為合成是多層的，并且合成方案還不唯一。我們需要一個更加簡單的子問題。

設 \(f_{l,r}\) 表示將 \(T[l,r]\) 中的字母合成一個字母，可以合成出的字母的集合。由于字母只有 \(26\) 個，所以可以狀壓。

這樣是好轉移的：

其中 \(\operatorname{calc}\) 求的是兩邊集合中的字符可以合成出的字符集合，可以在 \(O(|\Sigma|^2)\) 的時間內求出，\(|\Sigma|\) 為字符集大小。

對于統計答案，可以使用我們之前棄用的狀態。設 \(g_{l,r}\) 表示合成 \(T[l,r]\) 中的字符后得到的最少 \(\texttt{S}\) 個數。

那么，若 \(\texttt{S} \in f_{l,r}\)：

否則：

\(g_{1,len}\) 即為所求。

于是，我們在 \(O(|\Sigma|^2\cdot L^3\cdot k)\) 的時間內解決了這個問題。

代碼

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 26 + 5,M = 100 + 5;
int can[N][N],f[M][M],g[M][M];
int calc(int a,int b){
	int res = 0;
	for(int i=0;i<26;i++)if(a & (1 << i)){
		for(int j=0;j<26;j++)if(b & (1 << j)){
			res |= can[i][j]; 
		}
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		can[s[1] - 'A'][s[2] - 'A'] |= 1 << (s[0] - 'A');
	}
	int k;
	cin>>k;
	while(k--){
		string t;
		cin>>t;
		int m = t.size();
		for(int i=1;i<=m;i++){
			for(int j=1;j<=m;j++){
				g[i][j] = 2.1e9;
				f[i][j] = 0;
			}
		}
		t = " " + t;
		for(int i=1;i<=m;i++){
			f[i][i] = 1 << (t[i] - 'A');
		}
		for(int len = 2;len <= m;len++){
			for(int l=1;l + len - 1<=m;l++){
				int r = l + len - 1;
				for(int k=l;k<r;k++){
					f[l][r] |= calc(f[l][k],f[k + 1][r]);
				}
				if(f[l][r] & (1 << ('S' - 'A'))){
					g[l][r] = 1;
				}else{
					for(int k=l;k<r;k++){
						g[l][r] = min(1ll * g[l][r],1ll * g[l][k] + g[k + 1][r]);
					}
				}
			}
		}
		if(g[1][m] > 2e9){
			cout<<"NIE\n";
		}else{
			cout<<g[1][m]<<'\n';
		}
	}
	return 0;
}