HardRating 2073
1799. Maximize Score After N Operations
arraymathdynamic-programmingbacktrackingbit-manipulationnumber-theorybitmask
解題說明
Maximize Score After N Operations
題目描述：
給定一個長度為 2n 的正整數陣列 nums。執行 n 次操作，第 i 次操作（i = 1, 2, ..., n）選擇兩個尚未使用的元素 nums[x] 和 nums[y]，得到分數 i * gcd(nums[x], nums[y])。求最大總分。
解題思路：
由於 2n <= 14（即最多 14 個元素），可以用 位元遮罩 DP（Bitmask DP）。
- 用一個整數
mask表示哪些元素已被使用。 dp[mask]= 已使用 mask 中元素所能獲得的最大分數。- 當前是第幾次操作可由
popcount(mask) / 2算出。 - 預處理所有配對 (i, j) 的
gcd(nums[i], nums[j])。 - 對每個 mask，嘗試所有未使用的配對 (i, j) 進行轉移。
為了避免重複計算相同配對的不同順序，只枚舉 i < j。
C++ 解法
複雜度分析
時間複雜度：O(2^(2n) · n²) — 枚舉所有 2^(2n) 個 mask，每個 mask 嘗試 O(n²) 個配對。2n ≤ 14 時約為 16384 × 49 ≈ 80 萬次操作。
空間複雜度：O(2^(2n) + n²) — DP 陣列 O(2^(2n))，GCD 預計算表 O(n²)。
虛擬碼
1. Let m = nums.size(), n = m / 2
2. Precompute gcd[i][j] for all pairs 0 <= i < j < m
3. Create dp array of size 2^m, initialized to 0
4. For each mask from 0 to 2^m - 1:
a. bits = popcount(mask)
b. If bits is odd, skip
c. op = bits / 2 + 1 (next operation number)
d. If op > n, skip
e. For each pair (i, j) where i < j and neither is in mask:
- newMask = mask | (1 << i) | (1 << j)
- dp[newMask] = max(dp[newMask], dp[mask] + op * gcd[i][j])
5. Return dp[(1 << m) - 1]其他解法
記憶化遞迴 + Bitmask O(2^(2n) · n²)：用 dfs(mask) 遞迴搜索，以 mask 為記憶化鍵。本質與迭代 DP 相同，但遞迴寫法更直觀，只訪問可達狀態，實際效率可能更好。
回溯暴力 O((2n)!!)：嘗試所有配對排列。(2n-1)!! 的雙階乘增長極快，2n=14 時為 135135，雖能通過但遠不如 bitmask DP 優雅。
延伸思考
- 如果操作分數改為
i * lcm(nums[x], nums[y])，演算法需要如何修改？ - 如果 nums 長度增大到 20 或更多，bitmask DP 不再可行，有什麼替代方案？
- 如果要求最小化總分（而非最大化），貪心策略是否有效？