Leetcode.1799 N 次操作后的最大分数和

题目链接

Leetcode.1799 N 次操作后的最大分数和 Rating ： 2073

题目描述

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

在第 i 次操作时（操作编号从 1 开始），你需要：

• 选择两个元素 x 和 y 。
• 获得分数 $i\ast 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\ast n$
• $1<=nums[i]<=10^6$

解法：状压dp

预处理：

定义一个二维数组 $g$，$g[i][j]=gcd(nums[i],nums[j])$，方便我们快速的获得 $nums[i]和nums[j]$ 的最大公因数。

$m=nums.size()$，我们用一个二进制数 $2^m$ 表示 $nums[i]$ 选还是不选。

我们定义 $f(mask)$ 为状态是 $mask$ 的情况下的最大分数和，按照定义，$f(2^m-1)$ 就是答案。

限制：$mask$中 1 的个数（我们用 $k$ 来表示） 必须是偶数，因为我们每次都是选择两个数进行操作的。

当前状态为 $mask$，选择了 $nums[i]和nums[j]$ 的情况：
f ( m a s k ) = m a x { f ( m a s k ) , f ( m a s k − ( 2 i ) − ( 2 j ) ) + k / 2 ∗ g [ i ] [ j ] } f(mask) = max \{ f(mask) , f(mask - (2^i) - (2^j)) + k/2 * g[i][j] \} f(mask)=max{f(mask),f(mask−(2i)−(2j))+k/2∗g[i][j]}。

时间复杂度： $O(m^{2}logC+2^m\ast m^2)$

C++代码：

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int m = nums.size();
        int g[m][m];
        for(int i = 0;i < m;i++){
            for(int j = i + 1;j < m;j++){
                g[i][j] = gcd(nums[i],nums[j]);
            }
        }

        int len = (1 << m);
        int f[len];
        memset(f,0,sizeof f);

        for(int mask = 3;mask < len;mask++){
            int k = __builtin_popcount(mask);
            if(k & 1) continue;
            for(int i = 0;i < m;i++){
                if((mask >> i) & 1){
                    for(int j = i + 1;j < m;j++){
                        if((mask >> j) & 1){
                            f[mask] = max(f[mask] , f[mask ^ (1 << i) ^ (1 << j)] +k/2*g[i][j]);
                        }
                    }
                }
            }
        }

        return f[len-1];
    }
};