URAL 1143 Electric Path：凸包上最短哈密頓路徑 DP 解法

題目與性質

給定逆時針頂點的凸包（n ≤ 200），求最短哈密頓路徑長度（訪問每個頂點恰好一次）。關鍵性質：凸包上最短哈密頓路徑不存在邊交叉。因此路徑從某點出發，每步只能連接順時針或逆時針相鄰的未訪問點。

DP 狀態定義

• ans[i][j][0]：從頂點 i 出發，向後（順時針）覆蓋 j 個頂點的最短路徑長度，當前在區間左端點
• ans[i][j][1]：同理，當前在區間右端點
• 區間始終保持連續，未訪問點在區間外

轉移方程

// 當前在左端點 i，區間長度 j
ans[i][j][0] = min(
    ans[i+1][j-1][0] + dist(i, i+1),        // 向左擴展，停在新左端點
    ans[i+j][j-1][1] + dist(i, i+j)         // 跨過整個區間到右端點，停在右端點
);

// 當前在右端點 i，區間長度 j
ans[i][j][1] = min(
    ans[i-1][j-1][1] + dist(i, i-1),        // 向右擴展
    ans[i-j][j-1][0] + dist(i, i-j)         // 跨過區間到左端點
);

求解流程

1. 預計算所有點對距離 dist[i][j]
2. 枚舉起始點 t（0~n-1），將頂點循環移位使 t 為 0
3. 遞歸 + 記憶化搜索 dfs(i, j, st) 計算 ans
4. 最終答案：min(dfs(1,n-2,0)+dist(0,1), dfs(n-1,n-2,1)+dist(0,n-1))
5. 全局最小值遍歷所有 t

複雜度

• 狀態數：n × n × 2 ≈ 80000
• 每狀態 O(1) 轉移，總 O(n³) ≈ 800萬操作，極快
• 記憶化避免重複計算，棧深 ≤ n

代碼關鍵片段

double dfs(int i,int j,int st) {
    i=(i+n)%n;
    if(ans[i][j][st]>eps) return ans[i][j][st];
    if(j==1) return ans[i][j][st]=getdis(i,i+(st?-1:1));
    if(!st)
        return ans[i][j][st]=min(dfs(i+1,j-1,0)+getdis(i,i+1),
                                 dfs(i+j,j-1,1)+getdis(i,i+j));
    else
        return ans[i][j][st]=min(dfs(i-1,j-1,1)+getdis(i,i-1),
                                 dfs(i-j,j-1,0)+getdis(i,i-j));
}

總結

利用凸包幾何性質將 NP-Hard 的 TSP 降為多項式 DP，狀態設計巧妙體現「區間擴展」思想，是幾何 DP 經典範例。