Hihocoder 1170 機器人排序：狀態壓縮 DP 解決顏色分組最小交換次數

問題大意

N ≤ 15 個機器人排成一列，每個有顏色（≤16 種）。相鄰交換，求將同顏色機器人聚在一起的最小交換次數。

關鍵結論

相同顏色機器人相對順序不變（交換同色無意義）。問題等價於：決定 顏色段的排列順序，共有 K! (K≤16) 種。最小交換次數 = 逆序對數。

狀態壓縮 DP（旅行商問題風格）

• dp[mask]：已安排顏色集合為 mask 時的最小交換次數
• 轉移：枚舉下一個加入的顏色 c，成本 = 當前 c 色機器人需要跳過的其他顏色機器人數

預處理成本

cost[c][mask]：在已安排 mask 的前提下，將顏色 c 放到末尾的代價。可通過前綴和 O(K·2^K) 預處理，或 O(K²·2^K) 直接計算。

兩種實現

1. 記憶化搜索 O(K²·2^K)

LL dfs(int mask) {
    if (dp[mask] != -1) return dp[mask];
    dp[mask] = INF;
    for (int c=0; c

for (int mask=1; mask < (1<