D.愚人节快乐 | 2018 校内选拔赛 练习赛

Description

愚人节到了,祝大家节日快乐~作为源代码的主要领导人,DarkZero同学想了个愚弄大家的好办法——送礼物。嘿嘿,不要想的太好,哪儿能给你们那么轻易空手套白狼,DarkZero为了愚人,准备了很多套娃,其中有一个套娃里面装了礼物,这个套娃里也可能还有套娃,为的就是让你稍微不注意就没看到礼物。套娃里面可以再放若干个套娃,也可以不放,完全看他心情。用[]表示一个套娃,G表示礼物,DarkZero想让你帮他算出愚人指数,即运气最好的人需要打开多少个套娃就能拿到礼物。

Input

第一行包含一个整数T,代表测试样例数。
接下来每行代表一个测试样例,每行中有一个字符串,包含'[‘,’]’和’G’三种字符。每行长度不超过200。

Output

对每个测试样例输出一行,一行中包含一个数字,代表最少需要打开的套娃数。

Sample Input

2
[[G]]
[G][]

Sample Output

2
1

Hint

这道题目可以使用简单的动态规划来求解,或者使用搜索加剪枝的方法。测试样例有很多,写的不好可能会超时。(以上提示写于2015年愚人节)

题解

#define INF
#define offline
#include "bits/stdc++.h"
using namespace std;
int main()
{
    //std::ios_base::sync_with_stdio(false);
    //std::cin.tie(0);
    //srand((unsigned int)(time(NULL)));
    int Case;
    scanf("%d", &Case);
    getchar();//去除换行
    for (int T = 0; T < Case; T++)
    {
        char str[210];
        int i = 0;
        char c;
        c = getchar();
        int l = 0, r = 0;
        bool flag = 0;
        //遇到 G 之前
        while (c != 'G')
        {
            if (c == '[')
                l++;
            else
                if (l > 0)
                    l--;
            c = getchar();
        }
        
        //遇到 G 之后
        while (c != '\n')
        {
            if (c == ']')
                r++;
            else
                if (r > 0)
                    r--;
            c = getchar();
        }
        printf("%d\n", min(l, r));
    }
    return 0;
}

CC BY-SA 4.0 D.愚人节快乐 | 2018 校内选拔赛 练习赛 by 小小泥娃的部落格 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论