Light OJ 1051 - Good or Bad

时间：2021-03-22 20:27:24

题目大意： 给你一个字符串，字符串由大写字母和‘？’组成，大写字母可以变成任意一个字母。现在我们定义字符串， 如果有超过三个连续的元音字母或者连续五个辅音字母，那么我们称这个字符串是“BAD”，否则称这个字符串是“GOOD”, 如果字符串既可以是“GOOD”又可以是 “BAD” 那么我们称这个字符串是“MIXED”.

题目分析：
刚开始做的时候确实没做出来，后来看了题解，确实是有点脑洞的，之前一直想不出怎么去DP。
dp[字符串的第i个位置][以第i个位置为终点连续最长的元音为i是否存在][连续最长为j是否存在] = 这个状态是否存在。
在这个DP过程中，一旦第i个位置出现了长度为3的元音或者长度为5的辅音的时候，我们后面的DP式子就不会再出现存在的情况了。
 
 
#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

const int INF = 1e9+;

const int MAXN = ;

bool dp[MAXN][][];///dp[位置][元音][辅音]

char str[MAXN];

bool OK(char ch)

{

    return ch == 'A' || ch == 'E' || ch == 'O' || ch == 'I' || ch == 'U';

}

void solve(int n)

{

    memset(dp, false, sizeof(dp));

    dp[][][] = true;

    for(int i=; i<=n; i++)

    {

        for(int j=; j<=; j++)

        {

            if(str[i] == '?' || !OK(str[i]))///辅音

                dp[i][][j+] |= dp[i-][][j];

            if(str[i] == '?' ||  OK(str[i]))

                dp[i][][] |= dp[i-][][j];

        }

        for(int j=; j<=; j++)

        {

            if(str[i] == '?' || OK(str[i]))

                dp[i][j+][] |= dp[i-][j][];

            if(str[i] == '?' || !OK(str[i]))

                dp[i][][] |= dp[i-][j][];

        }

    }

    int good = , bad = ;

    for(int i=; i<=; i++)

    if(dp[n][][i]) good = ;

    for(int i=; i<=; i++)

    if(dp[n][i][]) good = ;

    for(int i=; i<=n; i++)

    if(dp[i][][] || dp[i][][]) bad = ;

    if(good && bad) puts("MIXED");

    else if(good) puts("GOOD");

    else puts("BAD");

}

int main()

{

    int T, cas = ;

    scanf("%d", &T);

    while(T --)

    {

        scanf("%s", str + );

        printf("Case %d: ", cas ++);

        solve(strlen(str+));

    }

    return ;

}

相关文章