LeetCode 5695. N 次操作后的最大分数和(回溯)

  • 时间:
  • 浏览:
  • 来源:互联网

文章目录

    • 1. 题目
    • 2. 解题
      • 2.1 错误解
      • 2.2 回溯超时解
      • 2.3 回溯通过

1. 题目

给你 nums ,它是一个大小为 2 * n 的正整数数组。
你必须对这个数组执行 n 次操作。

在第 i 次操作时(操作编号从 1 开始),你需要:

  • 选择两个元素 xy
  • 获得分数 i * gcd(x, y)
  • xynums 中删除。

请你返回 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++


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

长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
Michael阿明

本文链接http://www.dzjqx.cn/news/show-617405.html