一道很不错的DP
要是没提示的话 肯定想不出来的说
两次DP~
题目：
题目 - 基因串 来源 POI 描述 基因串是由一串有限长度的基因所组成的，其中每一个基因都可以用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推导得出),即得到原问题的解.
code：
#include<iostream>using namespace std;struct Rule{ int st; int ed1; int ed2;};Rule rules[100];int f[105][105][30];int g[105][105];int main(){ int n,i,l,st,k,j,c; char tr[4]; char s[200]; scanf("%d",&n); gets(tr); for(i=1;i<=n;i++) { gets(tr); rules[i].st = tr[0] - ‘A’; rules[i].ed1 = tr[1] - ‘A’; rules[i].ed2 = tr[2] - ‘A’; } gets(s); memset(f,0,sizeof(f)); for(i=0;i<strlen(s);i++) { f[i][i][s[i]-‘A’] = 1; } for(l=2;l<= strlen(s);l++) { for(st=0 ;st + l <= strlen(s) ;st++) { for(i = 1 ; i<=n ; i++) { for(k = st ; k< st +l -1;k++ ) { f[st][st+l-1][rules[i].st] |= ( f[st][k][rules[i].ed1] f[k+1][st+l-1][rules[i].ed2]); } } } }// for(i = 0 ;i<strlen(s);i++)// {// for(j=0 ; j< strlen(s);j++)// {// for(c = 0 ; c<26;c++)// {// if(f[i][j][c]) cout<<"i="<<i<<" j="<<j<<" c="<<char(c+’A’)<<endl;// }// }// } for(i = 0 ;i<strlen(s) ;i++) for(j = 0; j<strlen(s);j++) g[i][j] = 10000; for(l=1;l<= strlen(s);l++) { for(st=0 ;st + l <= strlen(s) ;st++) { if(f[st][st+l-1][‘S’-‘A’]) { g[st][st+l-1] = 1; } else { for(k = st; k< st + l -1 ; k++) { if(g[st][k] + g[k+1][st+l-1] < g[st][st+l-1]) g[st][st+l-1] = g[st][k] + g[k+1][st+l-1]; } } } } if(g[0][strlen(s)-1]>=1000) g[0][strlen(s)-1] = -1; printf("%dn",g[0][strlen(s)-1]); return 0;} 提示 Case 0: Time = 23ms, Memory = 264kB.Case 1: Time = 26ms, Memory = 264kB.Case 2: Time = 22ms, Memory = 264kB.Case 3: Time = 22ms, Memory = 264kB.Case 4: Time = 46ms, Memory = 264kB.Case 5: Time = 29ms, Memory = 264kB.Case 6: Time = 85ms, Memory = 264kB.Case 7: Time = 88ms, Memory = 264kB.Case 8: Time = 176ms, Memory = 1472kB.Case 9: Time = 178ms, Memory = 1472kB.