跳转至

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

题目描述

给你 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] <= 106

解法

方法一：状态压缩 + 动态规划

我们可以先预处理得到数组 nums 中任意两个数的最大公约数，存储在二维数组 $g$ 中，其中 $g[i][j]$ 表示 $nums[i]$ 和 $nums[j]$ 的最大公约数。

然后定义 $f[k]$ 表示当前操作后的状态为 $k$ 时，可以获得的最大分数和。假设 $m$ 为数组 nums 中的元素个数，那么状态一共有 $2^m$ 种，即 $k$ 的取值范围为 $[0, 2^m - 1]$。

从小到大枚举所有状态，对于每个状态 $k$，先判断此状态的二进制位中 $1$ 的个数 $cnt$ 是否为偶数，是则进行如下操作：

枚举 $k$ 中二进制位为 1 的位置，假设为 $i$ 和 $j$，则 $i$ 和 $j$ 两个位置的元素可以进行一次操作，此时可以获得的分数为 $\frac{cnt}{2} \times g[i][j]$，更新 $f[k]$ 的最大值。

最终答案即为 $f[2^m - 1]$。

时间复杂度 $O(2^m \times m^2)$，空间复杂度 $O(2^m)$。其中 $m$ 为数组 nums 中的元素个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxScore(self, nums: List[int]) -> int:
        m = len(nums)
        f = [0] * (1 << m)
        g = [[0] * m for _ in range(m)]
        for i in range(m):
            for j in range(i + 1, m):
                g[i][j] = gcd(nums[i], nums[j])
        for k in range(1 << m):
            if (cnt := k.bit_count()) % 2 == 0:
                for i in range(m):
                    if k >> i & 1:
                        for j in range(i + 1, m):
                            if k >> j & 1:
                                f[k] = max(
                                    f[k],
                                    f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j],
                                )
        return f[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int maxScore(int[] nums) {
        int m = nums.length;
        int[][] g = new int[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[] f = new int[1 << m];
        for (int k = 0; k < 1 << m; ++k) {
            int cnt = Integer.bitCount(k);
            if (cnt % 2 == 0) {
                for (int i = 0; i < m; ++i) {
                    if (((k >> i) & 1) == 1) {
                        for (int j = i + 1; j < m; ++j) {
                            if (((k >> j) & 1) == 1) {
                                f[k] = Math.max(
                                    f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);
                            }
                        }
                    }
                }
            }
        }
        return f[(1 << m) - 1];
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 f[1 << m];
        memset(f, 0, sizeof f);
        for (int k = 0; k < 1 << m; ++k) {
            int cnt = __builtin_popcount(k);
            if (cnt % 2 == 0) {
                for (int i = 0; i < m; ++i) {
                    if (k >> i & 1) {
                        for (int j = i + 1; j < m; ++j) {
                            if (k >> j & 1) {
                                f[k] = max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);
                            }
                        }
                    }
                }
            }
        }
        return f[(1 << m) - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func maxScore(nums []int) int {
    m := len(nums)
    g := [14][14]int{}
    for i := 0; i < m; i++ {
        for j := i + 1; j < m; j++ {
            g[i][j] = gcd(nums[i], nums[j])
        }
    }
    f := make([]int, 1<<m)
    for k := 0; k < 1<<m; k++ {
        cnt := bits.OnesCount(uint(k))
        if cnt%2 == 0 {
            for i := 0; i < m; i++ {
                if k>>i&1 == 1 {
                    for j := i + 1; j < m; j++ {
                        if k>>j&1 == 1 {
                            f[k] = max(f[k], f[k^(1<<i)^(1<<j)]+cnt/2*g[i][j])
                        }
                    }
                }
            }
        }
    }
    return f[1<<m-1]
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function maxScore(nums: number[]): number {
    const m = nums.length;
    const f: number[] = new Array(1 << m).fill(0);
    const g: number[][] = new Array(m).fill(0).map(() => new Array(m).fill(0));
    for (let i = 0; i < m; ++i) {
        for (let j = i + 1; j < m; ++j) {
            g[i][j] = gcd(nums[i], nums[j]);
        }
    }
    for (let k = 0; k < 1 << m; ++k) {
        const cnt = bitCount(k);
        if (cnt % 2 === 0) {
            for (let i = 0; i < m; ++i) {
                if ((k >> i) & 1) {
                    for (let j = i + 1; j < m; ++j) {
                        if ((k >> j) & 1) {
                            const t = f[k ^ (1 << i) ^ (1 << j)] + ~~(cnt / 2) * g[i][j];
                            f[k] = Math.max(f[k], t);
                        }
                    }
                }
            }
        }
    }
    return f[(1 << m) - 1];
}

function gcd(a: number, b: number): number {
    return b ? gcd(b, a % b) : a;
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

评论