HDU 2577 How to Type (線性dp)

 

How to Type

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4616 Accepted Submission(s): 2084

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



題目大意：坑比題，給一些有大小寫組成的字符串，問用鍵盤打出它們的最少按鍵次數
按鍵規則：對於每一個小寫字母，加上shift可使其變成大寫，注意shift不可以一直按著不放，還可以開大寫鎖Caps lock鍵，按完這鍵輸入就變成大寫，此時再按shift，則打出小寫（mac的鍵盤貌似不是這樣），注意每次大寫鎖，最後必須把它關上

題目分析：知道題以後就很簡單了dp[i][0]和dp[i][1]分別表示到第i個字符大寫鎖關，開著時要按的最少次數，則有4種情況
如果到第i個字符為小寫且此時開著大寫鎖，則它前一個必然是大寫，因為如果前一個是小寫，當前也是小寫，我顯然不需要開大寫鎖
dp[i][1] = dp[i - 1][1] + 2
如果到第i個字符為小寫且此時沒開大寫鎖，直接打就行了
dp[i][0] = dp[i - 1][0] + 1
如果到第i個字符為大寫且此時開著大寫鎖，則為前一個開著大寫鎖的情況加1和前一個沒開大寫鎖的情況加2的最小值，表示開鎖
dp[i][1] = min(dp[i - 1][1] + 1, dp[i - 1][0] + 2)
如果到第i個字符為大寫且此時沒開大寫鎖，則為前一個沒開大寫鎖的情況加2(按shift)和前一個開著大寫鎖的情況加2的最小值，表示關鎖
dp[i][0] = min(dp[i - 1][0] + 2, dp[i - 1][1] + 2)

#include 
#include 
#include 
using namespace std;
int const MAX = 105;
char s[MAX];
int dp[MAX][2];

bool judge(char ch)
{
    if(ch >= 'A' && ch <= 'Z')
        return true;
    return false;
}

int main()
{
    int T;
    scanf(%d, &T);
    while(T--)
    {
        scanf(%s, s + 1);
        int len = strlen(s + 1);
        memset(dp,0, sizeof(dp));
        dp[0][1] =  1;
        for(int i = 1; i <= len; i++)
        {
            if(judge(s[i]))
            {
                dp[i][1] = min(dp[i - 1][1] + 1, dp[i - 1][0] + 2);
                dp[i][0] = min(dp[i - 1][0] + 2, dp[i - 1][1] + 2);
            }
            else
            {
                dp[i][1] = dp[i - 1][1] + 2;
                dp[i][0] = dp[i - 1][0] + 1;
            }
        }
        printf(%d
, min(dp[len][0], dp[len][1] + 1));
    }
}