UVA - 620Cellular Structure（递推）

题目：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 <cstdio>
#include <cstring>

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;
}

UVA - 620Cellular Structure（递推）,布布扣,bubuko.com

UVA - 620Cellular Structure（递推）

原文：http://blog.csdn.net/u012997373/article/details/38461057