毕竟水题，
可还是没能自己做出来。
不过有进步的是看了别人的解题思路便自己用代码实现了。
毕竟水题。
对状态转移方程的寻找还是没有什么思路，但有小小的体会：
所谓状态就是你开的dp数组能够记录从最开始的1个子问题最优解到最后整个状态的最优解。
首先你得dp数组得能记录每时每刻的状态，不能有信息丢失。
从打印第一个字符开始到最后一个字符，已经打印的字符的个数这是一个状态。
Caps Lock开没开这也是一个状态，所以这个题里面dp是两个维度。
而且状态转移方程的每次转换都要保证是从最优解转到最优解。
回到这个题上面来：
打字分这四种情况：
1、要打一个大写字母
①、打完这个字符大写锁定键是关着的
如果现在的状态时关着的，那么shift + key
如果现在的状态时开着的，那么CapsLock + key
②、打完这个字符大写锁定键是开着的
如果现在的状态时关着的，那么CapsLock + key
如果现在的状态时开着的，那么key
2、要打一个小写字母
①、打完这个字符大写锁定键是关着的
如果现在的状态时关着的，那么key
如果现在的状态时开着的，那么CapsLock + key
②、打完这个字符大写锁定键是开着的
如果现在的状态时关着的，那么key + CapsLock
如果现在的状态时开着的，那么shift + key
根据这个便可很容易的写出状态转移方程，具体见代码。
1 //#define LOCAL 2 #include3 #include 4 #include 5 #include 6 using namespace std; 7 8 int dp[110][2]; 9 10 int main(void)11 {12 #ifdef LOCAL13 freopen("2577in.txt", "r", stdin);14 #endif15 16 int n;17 char str[110];18 scanf("%d", &n);19 getchar();20 while(n--)21 {22 memset(dp, 0, sizeof(dp));23 gets(str + 1);24 int len = strlen(str + 1);25 dp[0][0] = 0;26 dp[0][1] = 1;27 int i;28 for(i = 1; i <= len; ++i)29 {30 if(str[i] >= 'A' && str[i] <= 'Z')31 {32 dp[i][0] = min(dp[i - 1][0] + 2, dp[i - 1][1] + 2);33 dp[i][1] = min(dp[i - 1][0] + 2, dp[i - 1][1] + 1);34 }35 else36 {37 dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 2);38 dp[i][1] = min(dp[i - 1][0] + 2, dp[i - 1][1] + 2);39 }40 }41 42 int ans = min(dp[len][0], dp[len][1] + 1);43 printf("%d\n", ans);44 }45 return 0;46 }