题意： 给出一个由大小写字母组成的字符串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
     
       2 #include
      
        3 #include
       
         4 #include
        
          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\n", min(dp[len][0], dp[len][1]+1));31     }32     return 0;33 }