【题意】:给出一个长度为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 }