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