·天新网首页·加入收藏·设为首页·网站导航
数码笔记本手机摄像机相机MP3MP4GPS
硬件台式机网络服务器主板CPU硬盘显卡
办公投影打印传真
家电电视影院空调
游戏网游单机动漫
汽车新车购车试驾
下载驱动源码
学院开发设计
考试公务员高考考研
业界互联网通信探索
您现在的位置:天新网 > 软件开发
UVA 620 Cellular Structure (dp)
http://www.21tx.com 2014年01月20日 CSDN 帆帆帆帆帆帆帆帆帆帆

Cellular Structure

A chain of connected cells of two types A and B composes a cellular structure of some microorganisms of species APUDOTDLS.

If no mutation had happened during growth of an organism, its cellular chain would take one of the following forms:

UVA 620 Cellular Structure (dp)

Sample notation O = OA means that if we added to chain of a healthy organism a cell A from the right hand side, we would end up also with a chain of a healthy organism. It would grow by one cell A.

A laboratory researches a cluster of these organisms. Your task is to write a program which could find out a current stage of growth and health of an organism, given its cellular chain sequence.

Input

A integer n being a number of cellular chains to test, and then n consecutive lines containing chains of tested organisms.

Output

For each tested chain give (in separate lines) proper answers:

UVA 620 Cellular Structure (dp)If an organism were in two stages of growth at the same time the first option from the list above should be given as an answer.

Sample Input

4
A
AAB
BAAB
BAABA

Sample Output

SIMPLE
FULLY-GROWN
MUTANT
MUTAGENIC

题意:如题,一个细胞有三种生长方式。求出当前细胞的上一个生长方式。 思路:由当前细胞一直往之前的状态找即可。直到找到结束或者不能再往下找了位置。 代码:

#include <stdio.h>
#include <string.h>
    
int t, len;
char ans[4][20] = {"SIMPLE", "FULLY-GROWN", "MUTANT", "MUTAGENIC"};
char str[1005];
    
int dp(int start, int end) {
    if (end - start == 1 && str[start] == 'A') {
        return 0;
    }
    else if (str[start] == 'B' && str[end - 1] == 'A') {
        if (dp(start + 1, end - 1) != 2) {
            return 3;
        }
    }
    else if (str[end - 1] == 'B' && str[end - 2] == 'A') {
        if (dp(start, end - 2) != 2) {
            return 1;
        }
    }
    return 2;
}
int main() {
    scanf("%d%*c", &t);
    while (t --) {
        gets(str);
        len = strlen(str);
        printf("%sn", ans[dp(0, len)]);
    }
    return 0;
}

上一篇: UVA 10029 - Edit Step Ladders(记忆化搜索)
下一篇: UVA 590 Always on the run(dp)

关于我们 | 联系我们 | 加入我们 | 广告服务 | 投诉意见 | 网站导航
Copyright © 2000-2011 21tx.com, All Rights Reserved.
晨新科技 版权所有 Created by TXSite.net