题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2577
题意：给一串只含大小写字母的字符串，问从键盘打出这个字符串最小需要按多少次按键？（可用Shift和Cap lock，初始Cap lock是关闭的，最终的状态Cap lock也必须是关闭的）
思路：利用DP可以很方便地解决。
dp[i][]表示打印完第i个字符最少需要的按键次数。
dp[i][0]时表示打印完第i个字符Cap lock是关闭的。
dp[i][1]时表示打印完第i个字符Cap lock是开启的。
很容易得出状态转移方程。
具体：
第i个字母是大写：
dp[i][0] =
min(dp[i-1][0] + 2, dp[i-1][1] + 2); //+shift， +Cap lock
dp[i][1] =
min(dp[i-1][0] + 2, dp[i-1][1] + 1); //+Cap lock， 不需转换
第i个字母是小写：
dp[i][0] =
min(dp[i-1][0] + 1, dp[i-1][1] + 2); //不需转换， +Cap lock
dp[i][1] = min(dp[i-1][0] + 2, dp[i-1][1] + 2);
//+Cap lock， +shift
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #define N 105
5
6 char s[N];
7 int dp[N][2];
8 int min(int x, int y)
9 {
10 return x > y ? y : x;
11 }
12
13 int main()
14 {
15 int t, len;
16 scanf("%d",&t);
17 while(t--)
18 {
19 scanf("%s",s+1);
20 len = strlen(s+1);
21 dp[0][0] = 0;
22 dp[0][1] = 1;
23 for(int i=1; i<=len; i++)
24 {
25 if(s[i]<‘a‘)
26 {
27 dp[i][0] = min(dp[i-1][0] + 2, dp[i-1][1] + 2);
28 dp[i][1] = min(dp[i-1][0] + 2, dp[i-1][1] + 1);
29 }
30 else
31 {
32 dp[i][0] = min(dp[i-1][0] + 1, dp[i-1][1] + 2);
33 dp[i][1] = min(dp[i-1][0] + 2, dp[i-1][1] + 2);
34 }
35 }
36 printf("%d\n",min(dp[len][0], dp[len][1] + 1));
37 }
38 return 0;
39 }
2 #include <cstring>
3 #include <cstdlib>
4 #define N 105
5
6 char s[N];
7 int dp[N][2];
8 int min(int x, int y)
9 {
10 return x > y ? y : x;
11 }
12
13 int main()
14 {
15 int t, len;
16 scanf("%d",&t);
17 while(t--)
18 {
19 scanf("%s",s+1);
20 len = strlen(s+1);
21 dp[0][0] = 0;
22 dp[0][1] = 1;
23 for(int i=1; i<=len; i++)
24 {
25 if(s[i]<‘a‘)
26 {
27 dp[i][0] = min(dp[i-1][0] + 2, dp[i-1][1] + 2);
28 dp[i][1] = min(dp[i-1][0] + 2, dp[i-1][1] + 1);
29 }
30 else
31 {
32 dp[i][0] = min(dp[i-1][0] + 1, dp[i-1][1] + 2);
33 dp[i][1] = min(dp[i-1][0] + 2, dp[i-1][1] + 2);
34 }
35 }
36 printf("%d\n",min(dp[len][0], dp[len][1] + 1));
37 }
38 return 0;
39 }