SERC 2013 J You Win!：狀態壓縮 DP 求最少按鍵次數輸入名字

問題描述

手柄輸入大寫字母 A-Z（循環）。操作：

• UP/DN：字母前進/後退（A↑→B，A↓→Z）。
• L/R：游標在已輸入名字中左右移動（不可越界）。
• FIRE：在游標處插入當前字母。

初始字母 A，游標在空名字最右。求輸入給定名字（長度 1~18）的最少按鍵數。

狀態壓縮 DP

• 狀態 mask：已放置字母的集合（第 i 位 = 1 表示原名字第 i 字母已放入）。
• dp[mask][pos]：狀態 mask 下，游標在第 pos 個字母右側（pos=0 為最左）的最小按鍵數。
• 轉移：從 mask' = mask ^ (1<<k)（移除第 k 字母）到 mask，游標從 pos' 移到 pos=k+1，字母從 str[pos'-1] 變到 str[k]。
• 代價 = 字母變換步數 + 游標移動步數（穿過已放字母） + 1（FIRE）。

核心代碼

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[1<<19][19], n; char str[20];
int getD(char a, char c) { if (a > c) swap(a, c); return min(c - a, a - 'A' + 'Z' - c + 1); }
int getSHIFT(int from, int to, int st) { // 計算游標穿過已放字母的步數
    int ans = 0;
    if (from < to) for (int i = from; i < to; i++) if (st & (1<<i)) ans++;
    else for (int i = from - 1; i > to - 1; i--) if (st & (1<<i)) ans++;
    return ans;
}
void solve() {
    memset(dp, 63, sizeof(dp));
    for (int i = 0; i < 19; i++) dp[0][i] = 0;
    for (int i = 0; i < n; i++) dp[1<<i][i+1] = getD('A', str[i]) + 1; // 首字母
    for (int i = 1; i < (1<<n); i++) {
        for (int j = 1; j <= n; j++) if (i & (1<<(j-1))) {
            int k = j - 1, ii = i ^ (1<<k);
            for (int jj = 1; jj <= n; jj++) if (ii & (1<<(jj-1))) {
                dp[i][j] = min(dp[i][j], dp[ii][jj] + getD(str[jj-1], str[j-1]) + getSHIFT(jj, j, ii) + 1);
            }
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i++) ans = min(ans, dp[(1<<n)-1][i]);
    printf("%d\n", ans);
}
int main() {
    while (scanf("%s", str) != EOF) {
        if (str[0] == '0') break;
        n = strlen(str); solve();
    }
    return 0;
}

複雜度分析

• 狀態數 2ⁿ × n，n ≤ 18 → 約 470 萬狀態。
• 轉移 O(n)，總時間 O(n² 2ⁿ) ≈ 8×10⁷，C++ 1s 內可過。
• 空間 O(n 2ⁿ) ≈ 9 MB。

樣例

ALMA → 17
YES  → 19