首页 > 代码库 > UVA - 620Cellular Structure(递推)

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 stageMUTANT; )


代码:

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