文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 錯誤解
    • 2.2 回溯超時解
    • 2.3 回溯通過
    • 2.4 狀態壓縮DP

1. 題目

給你 nums ，它是一個大小為 2 * n 的正整數數組。
你必須對這個數組執行 n 次操作。

在第 i 次操作時（操作編號從 1 開始），你需要：

• 選擇兩個元素 x 和 y 。
• 獲得分數 i * gcd(x, y) 。
• 將 x 和 y 從 nums 中刪除。

請你返回 n 次操作后你能獲得的分數和最大為多少。

函數 gcd(x, y) 是 x 和 y 的最大公約數。

示例 1： 輸入：nums = [1,2] 輸出：1 解釋：最優操作是： (1 * gcd(1, 2)) = 1示例 2： 輸入：nums = [3,4,6,8] 輸出：11 解釋：最優操作是： (1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11示例 3： 輸入：nums = [1,2,3,4,5,6] 輸出：14 解釋：最優操作是： (1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14提示： 1 <= n <= 7 nums.length == 2 * n 1 <= nums[i] <= 10^6

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximize-score-after-n-operations
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 錯誤解

• 貪心取最大的得分組合，有可能不是最佳方案，[481851,31842,817070,452937,627635,712245]最后的例子過不了

class Solution { public:int maxScore(vector<int>& nums) {vector<vector<int>> g(nums.size(),vector<int>(nums.size()));priority_queue<tuple<int, int, int, int>> q;for(int i = 0; i < nums.size(); ++i){for(int j = i+1; j < nums.size(); ++j){g[i][j] = __gcd(nums[i], nums[j]);for(int k = 1; k <= nums.size()/2; ++k){q.push(tuple(k*g[i][j], i, j, k));}}}vector<bool> vis(nums.size(), false), visk(nums.size()/2+1, false);int count = nums.size()/2;int ans = 0;while(count){auto [p, i, j, k] = q.top();q.pop();if(vis[i] || vis[j] || visk[k])continue;vis[i] = true;vis[j] = true;visk[k] = true;count--;ans += p;}return ans;} };

2.2 回溯超時解

• 通過 46/66

class Solution {int maxS = 0; public:int maxScore(vector<int>& nums) {vector<bool> vis(nums.size(), false);sort(nums.begin(),nums.end());vector<vector<int>> g(nums.size(),vector<int>(nums.size()));for(int i = 0; i < nums.size(); ++i){for(int j = i+1; j < nums.size(); ++j){g[i][j] = __gcd(nums[i], nums[j]);}}dfs(nums, 0, 0, vis, g);return maxS;}void dfs(vector<int>& nums, int ct, int p, vector<bool>& vis, vector<vector<int>> &g){if(ct == nums.size()/2){if(p > maxS)maxS = p;return;}int i = 0, j;for( ; i < nums.size(); ++i){if(!vis[i]){vis[i] = true;for(j=i+1 ; j < nums.size(); ++j){if(!vis[j]){vis[j] = true;dfs(nums, ct+1, p+(ct+1)*g[i][j], vis, g);vis[j] = false;}}vis[i] = false;}} } };

2.3 回溯通過

class Solution {int maxS = 0; public:int maxScore(vector<int>& nums) {vector<bool> vis(nums.size(), false);vector<vector<int>> g(nums.size(),vector<int>(nums.size()));for(int i = 0; i < nums.size(); ++i){for(int j = 0; j < nums.size(); ++j){g[i][j] = __gcd(nums[i], nums[j]);}}vector<int> path;dfs(nums, 0, vis, g, path);return maxS;}void dfs(vector<int>& nums, int idx, vector<bool>& vis, vector<vector<int>> &g, vector<int>& path){if(idx == nums.size()/2){int s = 0;vector<int> v = path;sort(v.begin(), v.end());for(int i = 0; i < v.size(); i++){s += (i+1)*v[i];}maxS = max(maxS, s);return;}int i = 0, j = 0;for( ; i < nums.size(); ++i){if(vis[i]) continue;break;}vis[i] = true;for( ; j < nums.size(); ++j){if(!vis[j]){vis[j] = true;path.push_back(g[i][j]);dfs(nums, idx+1, vis, g, path);path.pop_back();vis[j] = false;}}vis[i] = false;} };

884 ms 82.7 MB C++

2.4 狀態壓縮DP

class Solution { public:int maxScore(vector<int>& nums) {int n = nums.size(), cti, ctj;vector<int> dp(1<<n);for(int i = 0; i < n; ++i){for(int j = i+1; j < n; ++j)dp[(1<<i)|(1<<j)] = __gcd(nums[i], nums[j]);}for(int i = 0; i < (1<<n); ++i){cti = count(i);if(cti%2 == 1) continue;for(int j = i; j>0; j=(j-1)&i){ctj = count(j);if(cti-ctj == 2)// 相差一對數，從 j 轉移到 i{dp[i] = max(dp[i], dp[j]+cti/2*dp[i^j]);}}}return dp[(1<<n)-1];}int count(int x){ // 計算二進制1個數int s = 0;while(x){s++;x = x&(x-1);}return s;} };

140 ms 8.2 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1799. N 次操作后的最大分数和（回溯 / 状态压缩DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。