Cho mảng nums kích thước 2n. Thực hiện n phép toán (1-indexed): chọn x,y, nhận điểm i * gcd(x,y), loại x,y. Tìm điểm tối đa sau n phép toán.
Ví dụ: nums = [6,2,1,5,4,3] → output = 14 (cặp (1,5), (2,4), (3,6) → 1·1 + 2·2 + 3·3 = 14).
Giải thuật (DP bitmask)
- n = len(nums). Trạng thái mask (2^n bit) biểu thị các phần tử đã dùng.
- dp[mask] = max điểm từ trạng thái mask. Khởi tạo -1.
- DFS(mask, t): nếu mask đầy → 0. Thử mọi cặp (i,j) chưa dùng, next = dfs(mask|1<
- Memoization dp[mask].
Code Python
from math import gcd
def solve(nums):
n = len(nums)
dp = [-1] * (1 << n)
def dfs(mask, t):
if mask == (1 << n) - 1:
return 0
if dp[mask] != -1:
return dp[mask]
ma = 0
for i in range(n):
if (1 << i) & mask:
continue
for j in range(i + 1, n):
if (1 << j) & mask:
continue
nxt = dfs(mask | (1 << i) | (1 << j), t + 1) + gcd(nums[i], nums[j]) * t
ma = max(ma, nxt)
dp[mask] = ma
return ma
return dfs(0, 1)
nums = [6, 2, 1, 5, 4, 3]
print(solve(nums)) # 14
Đầu vào / Đầu ra
Input: [6,2,1,5,4,3]
Output: 14