Giả sử chúng ta có một mảng gọi là nums, có kích thước là 2 * n. Chúng ta phải thực hiện n thao tác trên mảng này. Trong thao tác thứ i (được lập chỉ mục 1), chúng ta sẽ thực hiện như sau:
-
Chọn hai phần tử, x và y.
-
Nhận điểm i * gcd (x, y).
-
Xóa x và y khỏi số mảng.
Chúng ta phải tìm số điểm tối đa mà chúng ta có thể nhận được sau khi thực hiện n thao tác.
Vì vậy, nếu đầu vào giống như nums =[6,2,1,5,4,3], thì đầu ra sẽ là 14 vì các lựa chọn tối ưu là (1 * gcd (1,5)) + (2 * gcd ( 2, 4)) + (3 * gcd (3, 6)) =1 + 4 + 9 =14
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của nums
-
dp:=một mảng có kích thước (2 ^ n) và điền bằng -1
-
Định nghĩa một hàm dfs (). Điều này sẽ có mặt nạ, t
-
nếu mặt nạ giống như (2 ^ n - 1), thì
-
trả về 0
-
-
nếu dp [mask] không giống -1, thì
-
trả về dp [mask]
-
-
ma:=0
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
nếu 2 ^ i AND mask khác 0 thì
-
chuyển sang lần lặp tiếp theo
-
-
đối với j trong phạm vi i + 1 đến n - 1, thực hiện
-
nếu 2 ^ j AND mask khác 0 thì
-
chuyển sang lần lặp tiếp theo
-
-
next:=dfs (mask OR 2 ^ i OR 2 ^ j, t + 1) + gcd (nums [i], nums [j]) * t
-
ma:=tối đa của tiếp theo và ma
-
-
-
dp [mask]:=ma
-
trả về dp [mask]
-
Từ phương thức chính, trả về dfs (0, 1)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
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 next = dfs(mask | (1 << i) | (1 << j), t + 1) + gcd(nums[i], nums[j]) * t ma = max(next, ma) dp[mask] = ma return dp[mask] return dfs(0, 1) nums = [6,2,1,5,4,3] print(solve(nums))
Đầu vào
[6,2,1,5,4,3]
Đầu ra
14