这是一个思路新颖的动态规划问题，一看道题的时候看起来像搜索，一时没有想出动态规划。但是只要把思路变一下，要求给定的字串最少由几个S变换而成，每个自串能合成什么。
假设我们已经知道了，给定的串S，从第i位到第j位，能够合成的单个字母的集合，用G[i,j]表示，那么我们可以定义
F[i,j](1<=i,j<=L L为S长度)表示串S从第i位到第j位能够合成的S的最小个数
状态转移方程
F[i,j]=Min { F[i,k]+F[k+1,j] | i<=k<=j-1, 1 | ‘S’ 属于 G[i,j] }
边界条件
F[i,j]=∞
结果就是 F[1,L]
现在只需求出G[i,j]即可。我们定义H[A,B]为字母A,B能够合成的字母的集合，对于样例 SAB SBC SAA ACA BCC CBC 有 H[‘A’,‘B’]={‘S’} H[‘B’,‘C’]={‘S’,‘C’} H[‘A’,‘A’]={‘S’} H[‘C’,‘A’]={‘A’} H[‘C’,‘C’]={‘B’}
然后G[i,j]依然可以用动态规划求出。
状态转移方程
G[i,j]=Union{H[A,B] | A 属于 G[i,k] 且 B 属于 G[k+1,j] 且 i<=k<=j-1}
上式表示从G[i,k]和G[k+1,j]两个集合中，我们各取一个元素A，B，代表S[i,k]变换而成的A和S[k+1,j]变换而成的B，将A,B合成G[i,j]的一个元素。
边界条件 G[i,j]=Ø (1<=i,j<=L , i!=j) G[i,i]={S[i]}
以上的动态规划的方法是我第一次使用的，编程的时候要格外注意细节。关于集合的运算，我们可以用两个32位整型数保存每个字母的状态，用位运算的方法求是否包含每个元素，按位求或就是并集。
#include <iostream>
using namespace std;
class tSet
{
public:
unsigned int P;
tSet():P(0){}
bool Contain(int k)
{
return (P >> (k))&1;
}
void Union(tSet &k)
{
P |=k.P;
}
void Union(int k)
{
P |=1 << (k);
}
};
const int Target='S'-'A';
const int MAX_L=101;
const int INF=0x7FFFFFF;
int N,M,L,Ans;
char S[MAX_L];
tSet H[26][26];
tSet G[MAX_L][MAX_L];
int F[MAX_L][MAX_L];
void init()
{
int i,c,a,b;
freopen("gen.in","r",stdin);
freopen("gen.out","w",stdout);
scanf("%dn",&M);
for (i=1;i<=M;i++)
{
gets(S);
c=S[0]-'A';
a=S[1]-'A';
b=S[2]-'A';
H[a][b].Union(c);
}
scanf("%dn",&N);
}
void solve()
{
int i,j,k,a,b;
for (i=1;i<=L;i++)
{
for (j=1;j<=L;j++)
{
G[i][j].P=0;
}
G[i][i].Union((int)S[i-1]);
}
for (i=L;i>=1;i--)
{
for (j=i+1;j<=L;j++)
{
for (k=i;k<=j-1;k++)
{
for (a=0;a<26;a++)
{
for (b=0;b<26;b++)
{
if (G[i][k].Contain(a) && G[k+1][j].Contain(b))
{
G[i][j].Union(H[a][b]);
}
}
}
}
}
}
for (i=1;i<=L;i++)
{
for (j=1;j<=L;j++)
{
F[i][j]=INF;
}
}
for (i=L;i>=1;i--)
{
for (j=i;j<=L;j++)
{
if (G[i][j].Contain(Target))
{
F[i][j]=1;
}
else
{
for (k=i;k<=j-1;k++)
{
if (F[i][k]+F[k+1][j]<F[i][j])
{
F[i][j]=F[i][k]+F[k+1][j];
}
}
}
}
}
Ans=F[1][L];
}
int main()
{
init();
for (int i=1;i<=N;i++)
{
gets(S);
for (L=0;S[L];L++)
{
S[L]-='A';
}
solve();
if (Ans==INF)
printf("NIEn");
else
printf("%dn",Ans);
}
return 0;
}
基因串
基因串是由一串有限长度的基因所组成的，其中每一个基因都可以用26个英文大写字母中的一个来表示，不同的字母表示不同的基因类型。一个单独的基因可以生长成为一对新的基因，而可能成长的规则是通过一个有限的成长规则集所决定的。每一个成长的规则可以用三个大写英文字母A1A2A3来描述，这个规则的意思是基因A1可以成长为一对基因A2A3。
我们用大写字母S来表示一类被称作超级基因的基因。因为每一个基因串都是由一串超级基因根据给出的规则所成长出来的。
任务：
请写一个程序：
* 从文本文件中读入有限条成长的规则和一些我们想要得到的基因串；
* 对于每个基因串，试判断它是否可以由一个有限长度的超级基因串成长得出。如果可以，那么请给出可成长为该基因串的最短超级基因串的长度；
* 把结果输出到文本文件中。
输入格式：
在文本文件GEN.IN的第一行包括一个整数n，1 <= n <= 10000。以下的n行中每行都包括一个成长的规则，每个规则由三个大写英文字母组成。
在该文件的第n+1行包括一个整数k，1 <= k <= 10000。以下的k行中每行都有一个基因串。每个基因串都是一个长度不超过100的大写字符串。
输出格式：
在文件的第i（应共k行）行中你应该输出入下内容：
一个正整数，表示成长为改基因串所需的最短的超级基因串的长度；
或一个单词NIE（波兰语的“否”），如果说无法由超级基因串成长成为该基因串。
样例：
输入
6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA
输出
3
1
NIE
上次修改时间 2017-02-03