记录编号	577651	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 1997] 基因串	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.907 s
提交时间	2022-11-19 08:45:41	内存使用	3.88 MiB

// Problem: P6701 [POI1997] Genotype
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6701
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

const int maxn = 105;
const int INF = 0x3f3f3f3f;
int mp[30][30],n,m,f[maxn][maxn],QAQ[maxn][maxn];
char s[maxn];

void work() {
	scanf("%s",s + 1);
	n = strlen(s + 1);
	memset(f , 0x3f , sizeof(f));
	memset(QAQ , 0 , sizeof(QAQ));
	for(int i = 1;i <= n;++ i) {
		if(s[i] == 'S')f[i][i] = 1;
		QAQ[i][i] |= 1 << (s[i] - 'A');
	}
	for(int len = 2;len <= n;++ len) {
		for(int i = 1;i + len - 1 <= n;++ i) {
			int j = i + len - 1;
			for(int k = i;k < j;++ k) {
				f[i][j] = std::min(f[i][j] , f[i][k] + f[k + 1][j]);
				for(int p = 0;p < 26;++ p)
					for(int q = 0;q < 26;++ q)
						if((QAQ[i][k] >> p & 1)&&(QAQ[k + 1][j] >> q & 1))
							QAQ[i][j] |= mp[p][q];
			}
			if(QAQ[i][j] >> ('S' - 'A') & 1)f[i][j] = 1;
		}
	}
	if(f[1][n] >= INF)puts("NIE");
	else printf("%d\n",f[1][n]);
	return ;
}

int main() {
	freopen("gen.in","r",stdin);
	freopen("gen.out","w",stdout); 
	scanf("%d",&n);
	while(n --) {
		char a,b,c;
		scanf(" %c %c %c",&a,&b,&c);
		mp[b - 'A'][c - 'A'] |= 1 << (a - 'A');
	}
	scanf("%d",&m);
	while(m --)
		work();
	return 0;
}