POJ作业-基因串

题目描述：

基因串是由一串有限长度的基因所组成的，其中每一个基因都可以用26个英文大写字母中的一个来表示，不同的字母表示不同的基因类型。一个单独的基因可以生长成为一对新的基因，而可能成长的规则是通过一个有限的成长规则集所决定的。每一个成长的规则可以用三个大写英文字母A1A2A3来描述，这个规则的意思是基因A1可以成长为一对基因A2A3。
用大写字母S来表示一类称作超级基因的基因，因为每一个基因串都是由一串超级基因根据给出的规则所成长出来的。
请写一个程序，读入有限条成长的规则和一些我们想要得到的基因串，然后对于每个基因串，判断它是否可以由一个有限长度的超级基因串成长得出。如果可以，给出可成长为该基因串的最短超级基因串的长度。 关于输入 第一行为正整数n(n<=50)表示规则的数目。
接下来n行，每行一个规则。
最后一行是目标基因串，长度不超过100。

关于输出 输出最短的超级基因串的长度，如果无法生成，请输出-1

例子输入

3

BCA

ABC

SAB

BCCA

例子输出 1

乍看题目，好像无从下手，好在题目给了详尽的提示解法。

S->AB->BCB->BCCA
此题和石子归并问题类似,可以用f[i][j][C]表示从i到j的子串能否由C推导得出,f[i][j][C]=0表示不能,f[i][j][C]=1表示能,则有:
f[i][j][C]=max{f[i][k][A]*f[k+1][j][B]}其中i<=kAB是一条规则.
这样可以计算出每一段能否由一个超级基因S推导得出.
再由一次类似的动态规划过程可以算出每个子串最少由几个S推导得出(比如用g[i][j]表示从i到j的子串至少由几个S推导得出),即得到原问题的解.

所以，这道题很明显可以使用动态规划解决。

构建一个100*100*26（26为字母的数量）大小的bool型数组并不算大，用不了1M的空间即可。

而且，在程序运行中，大多数的空间是用不到的，因为仅有少数的字母可以用到。

代码：

// Author : Marchon

#include<iostream>

using namespace std;

bool f[100][100][26];

int Trans[50][3];

char Target[111];

int L,n;

void func()

{

for(int i = 0; i < L; i++)

{

f[i][0][Target[i]-'A'] = true;

}

for(int j = 1; j < L; j++)

{

for(int i = 0; i < L-j; i++)

{

for(int t = 0; t < n; t++)

{

int max = 0;

for(int k = 0; k < j; k++)

{

max += f[i][k][Trans[t][1]] * f[i+k+1][j-k-1][Trans[t][2]];

}

f[i][j][Trans[t][0]] += max;

}

}

}

}

int findS(int begin)

{

if(f[begin][L-begin-1][18])

return 1;

int result = 9999;

for(int i = L-1; i >= begin; i--)

{

if(f[begin][i-begin][18])

{

int temp = 1 + findS(i+1);

if(temp < result)

result = temp;

}

}

return result;

}

int main()

{

cin >> n;

for(int i = 0; i < n; i++)

{

char s,a,b;

cin >> s >> a >> b;

Trans[i][0] = s - 'A';

Trans[i][1] = a - 'A';

Trans[i][2] = b - 'A';

}

cin >> Target;

L = strlen(Target);

memset(f,0,sizeof(f));

func();

int min = findS(0);

if(min >= 9999)

cout << "-1" << endl;

else

cout << min << endl;

return 0;

}

Case 0: Time = 6ms, Memory = 272kB.
Case 1: Time = 12ms, Memory = 272kB.
Case 2: Time = 6ms, Memory = 272kB.
Case 3: Time = 6ms, Memory = 272kB.
Case 4: Time = 30ms, Memory = 272kB.
Case 5: Time = 18ms, Memory = 272kB.
Case 6: Time = 64ms, Memory = 272kB.
Case 7: Time = 73ms, Memory = 272kB.
Case 8: Time = 138ms, Memory = 392kB.
Case 9: Time = 141ms, Memory = 392kB.