【題意】：給出一個長度為n的字符串，只包含大小寫字母，問輸入這串字符串的最小按鍵次數，最終必須保證lock鍵是關閉的。

【題解】：可以這樣設定狀態，定義兩個數組on[],off[]。
               on[i]表示已經輸入了i個字母且lock是on狀態的最小按鍵次數
               off[i]表示已經輸入了i個字母且lock是off狀態的最小按鍵次數
               初始時 on[0] = 1, off[0] = 0;
               轉移方程：
                     大寫字母：               
                           on[i+1] = min(on[i] + 1, off[i] + 2);
                           off[i+1] = min(on[i] + 2, off[i] + 2);
                     小寫字母：
                           on[i+1] = min(on[i] + 2, off[i] + 2);
                           off[i+1] = min(on[i] + 2, off[i] + 1);
               顯然ans = min(on[len] + 1, off[len]);

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define maxn 105
 6 int on[maxn], off[maxn];
 7 char s[maxn];
 8 
 9 int main() {
10     int T;
11     scanf("%d", &T);
12     while(T--) {
13         scanf("%s", s);
14         int len = strlen(s);
15         on[0] = 1, off[0] = 0;
16         for(int i = 0; i < len; i++) {
17             if(s[i] >= 'a' && s[i] <= 'z') {
18                 on[i+1] = min(on[i] + 2, off[i] + 2);
19                 off[i+1] = min(on[i] + 2, off[i] + 1);
20             } else {
21                 on[i+1] = min(on[i] + 1, off[i] + 2);
22                 off[i+1] = min(on[i] + 2, off[i] + 2);
23             }
24         }
25         printf("%d\n", min(on[len] + 1, off[len]));
26     }
27     return 0;
28 }