题目：UVA - 620Cellular Structure（递推）

题目大意：只能给出三种细胞的增殖方式，然后给出最后细胞的增殖结果，最后问你这是由哪一种增殖方式得到的。如果可以由多种增殖方式得到，就输出题目中列出来的增殖方式靠前的那种。

解题思路：也是递推，细胞长度长的可以由细胞长度短的推得，并且这里第一种只能是长度为1的细胞才有可能，所以判断的时候可以3个判断，看能否与上面的增殖结果匹配，可以的话就记录下来，以后的长串就是由这样的短串再加上两个细胞继续往后推。

例如： BAABA 将A变为O ，这样BAA <==> BOA <== >O（mutagenic stage ），那么BAABA <==> OBA; AAB <==>O（simple stage）AB <==> O (fully-grown stage）,那么BAABA<==> BOA <==> O（mutagenic stage）。

状态转移方程：dp【i】【j】 = MIN（dp【i】【j - 2】 （是否原来的细胞增殖来的）？fully-grown stage：MUTANT， dp【i + 1][j - 1] (是否原来的细胞增殖来的）？mutagenic stage：MUTANT； ）

代码：

#include 
  
   
#include 
   
     const int N = 1005; const int M = 4; const char type[M][15] = {"SIMPLE", "FULLY-GROWN", "MUTAGENIC", "MUTANT"}; char str[N]; int dp[N][N]; int judge1 (int i, int j) { if (str[i] == 'A' && str[j] == 'B') return 1; return 0; } int judge2 (int i, int j) { if (str[i] == 'B' && str[j] == 'A') return 1; return 0; } int Min (const int a, const int b ) { return a < b ? a: b; } int main () { int t; int len; scanf ("%d", &t); while (t--) { scanf ("%s", str); len = strlen (str); for (int i = 1; i <= len; i++) if (str[i - 1] == 'A') dp[i][i] = 0; else dp[i][i] = 3; for (int i = 1; i <= len; i++) for (int j = i + 1; j <= len; j++) dp[i][j] = 3; for(int l = 2; l < len; l += 2) for (int i = 1; i + l <= len; i++) { dp[i][i + l] = 3; if (dp[i][i + l - 2] != 3 && judge1 (i + l - 2, i + l - 1)) dp[i][i + l] = Min (dp[i][i + l], 1); if (dp[i + 1][i + l - 1] != 3 && judge2 (i - 1, i + l - 1)) dp[i][i + l] = Min (dp[i][i + l], 2); } printf ("%s\n", type[dp[1][len]]); } return 0; }