题目

Description

Pirates have finished developing the typing software. He called Cathy to test his typing software. She is good at thinking. After testing for several days, she finds that if she types a string by some ways, she will type the key at least. But she has a bad habit that if the caps lock is on, she must turn off it, after she finishes typing. Now she wants to know the smallest times of typing the key to finish typing a string.

Input

The first line is an integer t (t<=100), which is the number of test case in the input file. For each test case, there is only one string which consists of lowercase letter and upper case letter. The length of the string is at most 100.

Output

For each test case, you must output the smallest times of typing the key to finish typing this string.

Sample Input

3
Pirates
HDUacm
HDUACM

Sample Output

8
8
8

Hint

The string “Pirates”, can type this way, Shift, p, i, r, a, t, e, s, the answer is 8. The string “HDUacm”, can type this way, Caps lock, h, d, u, Caps lock, a, c, m, the answer is 8 The string "HDUACM", can type this way Caps lock h, d, u, a, c, m, Caps lock, the answer is 8

翻译

背景

海盗们开发了打字软件
他们让善于思考的凯西来测试他的打字软件
测试了几天后,她发现她可以用不同的方式打不同的字母( Caps lock 、 shift )
但她有个坏习惯,如果使用大写锁定( Caps lock ),打完后必须要关掉它
现在她想知道输入一个字符串的最小完成时间

输入

第一行是数据数 t ( t<=100 )
接下来 t 行每行是一个只有大小写字母的字符串

输出

对于每组数据,在一行内输出最少花费的时间(按键数)

提示

对于 Pirates 可以这样输入 shift p i r a t e s 这样输入,共需要 8 个键
对于 HDUacm 可以这样输入 Cap Lock h d u Cap Lock a c m 这样输入,共需要 8 个键
对于 HDUACM 可以这样输入 Cap Lock h d u a c m Cap Lock 这样输入,共需要 8 个键

题解

自然,作为动态规划的题目,这道题可以使用动态规划求解,但是模拟相对会更快一点

首先,对于一个字符,需要判断大小写,同时需要一个变量记录 Cap Lock 是否开启,一个变量记录上一个字符
如果 Cap Lock 关闭,字符是小写;或者 Cap Lock 开启,字符是大写,直接把记录 +1 即可
如果 Cap Lock 和要输入的字符不同,就需要分类判断了
由于开始和最后 Cap Lock 是关闭的,要想维持这种状态必须需要按下两次 Cap Lock
如果只是一个键的键入,就不应该用 Cap Lock ,而是应该用 shift
而两个键时,两种方法效果相同,不过为了下一个字符的方便,还是变成 Cap Lock
不管是大写中有一个小写还是小写中有一个大写,都应该符合这些

字符输入完后,还需要判断 Cap Lock 的状态
在 AAa 形式的情况下,由于按照上面的情况,采取了使用 shift 的方法来保证最优(如果后面还有字符)
然而最后一个字符关掉 Cap Lock 才是最好的选择
因此,如果 Cap Lock 打开,并且最后一个字符是大写时,我们需要额外一次按键来保证关闭 Cap Lock

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

inline bool islower(char c) {
    return (c >= 'a'&&c <= 'z');
}
inline bool isupper(char c) {
    return (c >= 'A'&&c <= 'Z');
}

bool Do() {
    int dp=0;
    bool Cap = false;
    char c = getchar(),last = 'a';
    while(!(islower(c) || isupper(c)))
        c=getchar();
    while(islower(c) || isupper(c)) {
        if(islower(c)) {
            //字符是小写
            if(Cap) {
                if(islower(last)) {
                    dp += 1;
                    Cap = false;
                } else {
                    dp += 2;
                }
            } else {
                dp++;
            }
        } else {
            if(Cap) {
                dp++;
            } else {
                if(isupper(last)) {
                    dp++;
                    Cap = true;
                } else {
                    dp += 2;
                }
            }
        }
        last = c;
        c = getchar();
    }
    if(Cap)
        if(isupper(last))
            dp++;

    printf("%d\n",dp);

    return true;
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--)
        Do();
    return 0;
}