How to Type

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6656    Accepted Submission(s): 2999 Problem Description Pirates have finished developing the typing software. He called Cathy to test his typing software. She is good at thinking. After testing for several days, she finds that if she types a string by some ways, she will type the key at least. But she has a bad habit that if the caps lock is on, she must turn off it, after she finishes typing. Now she wants to know the smallest times of typing the key to finish typing a string.   Input The first line is an integer t (t<=100), which is the number of test case in the input file. For each test case, there is only one string which consists of lowercase letter and upper case letter. The length of the string is at most 100.   Output For each test case, you must output the smallest times of typing the key to finish typing this string.   Sample Input 3 Pirates HDUacm HDUACM   Sample Output 8 8 8 Hint The string “Pirates”, can type this way, Shift, p, i, r, a, t, e, s, the answer is 8. The string “HDUacm”, can type this way, Caps lock, h, d, u, Caps lock, a, c, m, the answer is 8 The string "HDUACM", can type this way Caps lock h, d, u, a, c, m, Caps lock, the answer is 8   Author Dellenge   Source HDU 2009-5 Programming Contest   Recommend lcy   |   We have carefully selected several similar problems for you:   2870  2830  2845  1058  2571  一个简单的动态规划题目： 做二维动态规划的几点注意： 1，首先注意dp[0][i],和dp[1][i]分别表示什么。 2，弄清楚状态转化方程 3，解决什么样的题目 感觉这个题目想到这个动态规划这个方法更为关键 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=105; int main() { int t; char a[N]; int dp[2][N];//分别代表小写状态和大写状态 scanf("%d",&t); while(t--) { memset(dp,0,sizeof(dp)); dp[0][0]=0;dp[1][0]=1; scanf("%s",a+1); int len=strlen(a+1); for(int i=1;a[i];i++) { if(a[i]>='A'&&a[i]<='Z') { dp[0][i]=min(dp[0][i-1]+2,dp[1][i-1]+2); dp[1][i]=min(dp[0][i-1]+2,dp[1][i-1]+1); } else if(a[i]>='a'&&a[i]<='z') { dp[0][i]=min(dp[0][i-1]+1,dp[1][i-1]+2); dp[1][i]=min(dp[0][i-1]+2,dp[1][i-1]+2); } } printf("%d\n",min(dp[0][len],dp[1][len]+1)); } return 0; }