[POI1997] Genotype

题目背景

Genotype 是一个独特的基因串。

题目描述

我们可以用大写英文字母 $A-Z$ 来描述 Genotype，每个字母就代表一个基因。

规定一种「分裂」规则，由三个大写字母 $A_1A_2A_3$ 组成，代表 $A_1$ 可以「分裂」为 $A_2A_3$。

现在给定 $n$ 个「分裂」规则和 $k$ 个 Genotype，判断这些 Genotype 是否能从一个特定的 只包含大写字母 $S$ 的 串通过「分裂」规则得到，如果可以的话输出特定的串的长度的最小值，如果不可以的话输出 NIE。

输入格式

第一行一个整数 $n$ 代表「分裂」规则数。
接下来 $n$ 行每行三个大写字母 $A_1,A_2,A_3$ 代表一个「分裂」规则。
接下来一行一个整数 $k$ 代表给定的 Genotype 数。
接下来 $k$ 行每行若干个大写字母表示一个 Genotype。

输出格式

$k$ 行：

• 如果没有特定的串通过「分裂」规则得到这个 Genotype，输出 NIE。
• 如果有特定的串通过「分裂」规则得到这个 Genotype，输出这个特定的串的最小长度。

样例 #1

样例输入 #1

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

样例输出 #1

3
1
NIE

提示

数据规模与约定

对于 $100%$ 的数据，$1 \le n,k \le 2000$，Genotype 的长度最大为 $100$。

#include<bits/stdc++.h>
using namespace std;
const int N=333;
int n,k;
int book[27][27],dv[N][N],f[N][N];//divide
//book[N][N]：两个字母能合并成一个字母 (规则) 
//dv[N][N]：两个区间都能合并成哪个字母  
//f[N][N]此区间能变成此S的区间的个数
//目标：把序列都变成S且S的数量最少 
char a[N];
int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
	{
		char ch;
		cin>>ch;
		int x = ch-'A'+1;
		cin>>ch;
		int y = ch-'A'+1;
		cin>>ch;
		int z = ch-'A'+1;
		book[y][z] |= 1 << x;
	}
	
	scanf("%d",&k);
	while(k--)
	{
		memset(dv,0,sizeof(dv));
		memset(f,0x3f,sizeof(f));
		
		scanf("%s",a+1);
		int le=strlen(a+1);
		
		for(int i = 1;i <= le;i++)
		{
			if(a[i] == 'S') f[i][i]=1;//能成S即为一 
			dv[i][i] |= (1<<(a[i]-'A'+1));//一个字母可以不变就是它自己 
		}
		
		for(int len = 1;len <= le;len++)
			for(int l = 1;l + len-1 <= le;l++)
			{
				int r=l+len-1;
				for(int k = l;k < r;k++)
				{
					f[l][r] = min(f[l][r],f[l][k] + f[k+1][r]);//取变成S最少的两个小区间
					for(int x = 1;x <= 26;x++)
						for(int y = 1;y <= 26;y++) 
							if((dv[l][k]&(1<<(x))) && (dv[k+1][r]&(1<<(y))))//两个小区间能变成的字母两两组合成新的字母继承给大区间 
								dv[l][r] |= book[x][y];
				}
				if(dv[l][r]&(1<<('S'-'A'+1))) f[l][r]=1;//整个区间能变成一个S 就直接等于一因为要最少 
			}
		
		if(f[1][le] >= 0x3f3f3f3f) printf("NIE\n");
		else printf("%d\n",f[1][le]);
	}
}