HDU-2577 How to Type（递推，DP）（水）2017寒假集训

题意：给出一个由大小写字母组成的字符串s，你的键盘初始状态是小写，你可以按一下shift切换一次大小写，或按Caps-Lock切换大小写，最后要把键盘恢复成小写，求打出这个字符串最少的按键次数

数据范围：|s| < 100 , t <= 100

思路：设dp[i][j]为前i个字母，状态为大写/小写时的最少按键次数

每次输入可以选择两种方式切换大小写

容易知道当s[i]为小写时，转移为dp[i][0] = min(dp[i-1][0]+1，dp[i-1][1]+2) 以此类推

最后答案为dp[n][0]和dp[n][1]+1中的较小者

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cctype>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int mx = 110;
 8 char s[mx];
 9 int dp[mx][2];
10 
11 int main(){
12     int t;
13     scanf("%d", &t);
14     while (t--){
15         memset(dp, 0, sizeof dp);
16         scanf("%s", s+1);
17         int len = strlen(s+1);
18         dp[0][0] = 0;
19         dp[0][1] = 1;
20         for (int i = 1; i <= len; i++){
21             if (islower(s[i])){
22                 dp[i][0] = min(dp[i-1][0]+1, dp[i-1][1]+2);
23                 dp[i][1] = min(dp[i-1][0]+2, dp[i-1][1]+2);
24             }
25             else {
26                 dp[i][0] = min(dp[i-1][0]+2, dp[i-1][1]+2);
27                 dp[i][1] = min(dp[i-1][0]+2, dp[i-1][1]+1);
28             }
29         }
30         printf("%d
", min(dp[len][0], dp[len][1]+1));
31     }
32     return 0;
33 }