diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /max_score_n_operations.cpp | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'max_score_n_operations.cpp')
-rw-r--r-- | max_score_n_operations.cpp | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/max_score_n_operations.cpp b/max_score_n_operations.cpp new file mode 100644 index 0000000..a2dc2b9 --- /dev/null +++ b/max_score_n_operations.cpp @@ -0,0 +1,59 @@ +// 1799. Maximize Score After N Operations +#include "leetcode.h" + +/* + * given 'nums', an array of positive integers of size '2 * n'. you must perform + * 'n' operations on this array. in the i'th operation (1-index), you will: + * - choose two elements 'x' and 'y' + * - receive a score of 'i * gcd(x, y)' + * - remove 'x' and 'y' from 'nums' + * return the maximum score you can receive after performing 'n' operations. the + * function 'gcd(x, y)' is the greatest common divisor. + */ + +class Solution { +public: + int maxScore(vector<int> nums) { + m = nums.size(); + n = m / 2; + return dp(nums, 1, 0); + } + +private: + int gcd_memo[14][14] = {}; + int memo[1 << 4] = {}; + int m, n; + int dp(vector<int> &nums, int op, int mask) { + if (op > n) + return 0; + if (memo[mask]) + return memo[mask]; + for (int i = 0; i < m; ++i) { + if ((mask >> i) & 0x1) + continue; + for (int j = i + 1; j < m; ++j) { + if ((mask >> j) & 0x1) + continue; + int new_mask = (0x1 << i) | (0x1 << j) | mask; + int score = op * gcd(nums, i, j) + dp(nums, op + 1, new_mask); + memo[mask] = max(memo[mask], score); + } + } + return memo[mask]; + } + int gcd(vector<int> &nums, int i, int j) { + if (gcd_memo[i][j]) + return gcd_memo[i][j]; + return gcd_memo[i][j] = __gcd(nums[i], nums[j]); + } +}; + +int main() { + Solution obj; + vector<int> n1 = {1, 2}; + vector<int> n2 = {3, 4, 6, 8}; + vector<int> n3 = {1, 2, 3, 4, 5, 6}; + printf("%d\n", obj.maxScore(n1)); // expect: 1 + printf("%d\n", obj.maxScore(n2)); // expect: 11 + printf("%d\n", obj.maxScore(n3)); // expect: 14 +} |