HDU 2577 How to Type 最少按鍵次數 DP/貪心雙解

輸入一字符串（含大小寫），需輸出該字符串。大寫可用 Shift+字母 或 Caps Lock 切換後輸入小寫再切回。初始與結束狀態均為 Caps Lock 關閉。求最少按鍵次數。

貪心解法（O(n)）

連續同大小寫段用 Caps Lock，單獨字符用 Shift。掃描字符串，維護 capslock 狀態：

• 當前字符大寫：
    若 !capslock，按鍵+1（Shift 或 Caps Lock）。
    若下一字符也大寫，開啟 capslock。
    按鍵+1（輸入字母）。
• 當前字符小寫：
    若 capslock，按鍵+1。
    若下一字符小寫或結束，關閉 capslock。
    按鍵+1。

最後若 capslock 開啟，額外 +1 關閉。

DP 解法（O(n)）

lock[i]：處理前 i 字符後 Caps Lock 開啟的最小按鍵數。
nolock[i]：同理關閉狀態。

轉移（大寫情況）：

lock[i]   = min(lock[i-1]+1, nolock[i-1]+2); // 保持開 / 從關開啟+輸入
nolock[i] = min(lock[i-1]+2, nolock[i-1]+2); // 關閉+輸入 / 保持關用Shift

小寫情況對稱。答案為 min(nolock[n-1], lock[n-1]+1)（結束需關閉）。

完整代碼（貪心版）

#include <cstdio>
#include <cstring>
#include <cctype>
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        char s[110]; scanf("%s", s);
        int len = strlen(s), ans = 0;
        bool capslock = false;
        for (int i = 0; i < len; ++i) {
            if (isupper(s[i])) {
                if (!capslock) ++ans;
                if (i+1 < len && isupper(s[i+1])) capslock = true;
                ++ans;
            } else {
                if (capslock) ++ans;
                if (i+1 == len || islower(s[i+1])) capslock = false;
                ++ans;
            }
        }
        if (capslock) ++ans;
        printf("%d\n", ans);
    }
    return 0;
}