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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你 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⁶

# 思路

状压DP

# 解法

class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length;

        // 预处理 gcd 数组
        int[][] g = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = gcd(nums[i], nums[j]);
            }
        }

        int[] f = new int[1 << n];
        for (int i = 0; i < 1 << n; i++) {
            int cnt = Integer.bitCount(i);
            for (int j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) {
                    for (int k = j + 1; k < n; k++) {
                        if (((i >> k) & 1) == 1) f[i] = Math.max(f[i], f[i ^ (1 << j) ^ (1 << k)] + cnt / 2 * g[j][k]);
                    }
                }
            }
        }
        return f[(1 << n) - 1];
    }

    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
30
31

# 总结

分析出几种情况，然后分别对各个情况实现

#Java