You are given nums
, an array of positive integers of size 2 * n
. You must perform n
operations on this array.
In the ith
operation (1-indexed), you will:
- Choose two elements,
x
andy
. - Receive a score of
i * gcd(x, y)
. - Remove
x
andy
fromnums
.
Return the maximum score you can receive after performing n
operations.
The function gcd(x, y)
is the greatest common divisor of x
and y
.
Example 1:
Input: nums = [1,2] Output: 1 Explanation: The optimal choice of operations is: (1 * gcd(1, 2)) = 1
Example 2:
Input: nums = [3,4,6,8] Output: 11 Explanation: The optimal choice of operations is: (1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
Example 3:
Input: nums = [1,2,3,4,5,6] Output: 14 Explanation: The optimal choice of operations is: (1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14
Constraints:
1 <= n <= 7
nums.length == 2 * n
1 <= nums[i] <= 106
Solution: Mask DP
dp(mask, i) := max score of numbers (represented by a binary mask) at the i-th operations.
ans = dp(1, mask)
base case: dp = 0 if mask == 0
Transition: dp(mask, i) = max(dp(new_mask, i + 1) + i * gcd(nums[m], nums[n]))
Time complexity: O(n2*22n)
Space complexity: O(22n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, 184 ms, 8.3 MB class Solution { public: int maxScore(vector<int>& nums) { const int l = nums.size(); vector<int> cache(1 << l); function<int(int)> dp = [&](int mask) { if (mask == 0) return 0; int& ans = cache[mask]; if (ans > 0) return ans; const int k = (l - __builtin_popcount(mask)) / 2 + 1; for (int i = 0; i < l; ++i) for (int j = i + 1; j < l; ++j) if ((mask & (1 << i)) && (mask & (1 << j))) ans = max(ans, k * gcd(nums[i], nums[j]) + dp(mask ^ (1 << i) ^ (1 << j))); return ans; }; return dp((1 << l) - 1); } }; |
Bottom-Up
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, 156 ms, 8.3 MB class Solution { public: int maxScore(vector<int>& nums) { const int l = nums.size(); vector<int> dp(1 << l); for (int mask = 0; mask < 1 << l; ++mask) { int c = __builtin_popcount(mask); if (c & 1) continue; // only do in pairs int k = c / 2 + 1; for (int i = 0; i < l; ++i) for (int j = i + 1; j < l; ++j) if ((mask & (1 << i)) + (mask & (1 << j)) == 0) { int new_mask = mask | (1 << i) | (1 << j); dp[new_mask] = max(dp[new_mask], k * gcd(nums[i], nums[j]) + dp[mask]); } } return dp[(1 << l) - 1]; } }; |