class Solution {
public:
int maxScore(vector<int>& nums) {
}
};
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 <= 7nums.length == 2 * n1 <= nums[i] <= 106原站题解
javascript 解法, 执行用时: 300 ms, 内存消耗: 50.1 MB, 提交时间: 2022-12-22 11:58:59
/**
* @param {number[]} nums
* @return {number}
*/
var maxScore = function(nums) {
const m = nums.length;
const dp = new Array(1 << m).fill(0);
const gcdTmp = 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) {
gcdTmp[i][j] = gcd(nums[i], nums[j]);
}
}
let all = 1 << m;
for (let s = 1; s < all; ++s) {
let t = bitCount(s);
if ((t & 1) !== 0) {
continue;
}
for (let i = 0; i < m; ++i) {
if (((s >> i) & 1) !== 0) {
for (let j = i + 1; j < m; ++j) {
if (((s >> j) & 1) !== 0) {
dp[s] = Math.max(dp[s], dp[s ^ (1 << i) ^ (1 << j)] + Math.floor(t / 2) * gcdTmp[i][j]);
}
}
}
}
}
return dp[all - 1];
}
const gcd = (num1, num2) => {
while (num2 !== 0) {
const temp = num1;
num1 = num2;
num2 = temp % num2;
}
return num1;
};
const bitCount = (n) => {
return n.toString(2).split('0').join('').length;
}
golang 解法, 执行用时: 32 ms, 内存消耗: 3.8 MB, 提交时间: 2022-12-22 11:58:35
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 max(a, b int) int {
if a > b {
return a
}
return b
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
cpp 解法, 执行用时: 36 ms, 内存消耗: 7.5 MB, 提交时间: 2022-12-22 11:58:09
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];
}
};
java 解法, 执行用时: 29 ms, 内存消耗: 40.6 MB, 提交时间: 2022-12-22 11:57:55
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);
}
}
python3 解法, 执行用时: 1528 ms, 内存消耗: 15.4 MB, 提交时间: 2022-12-22 11:57:41
'''
状态压缩 + 动态规划
我们可以先预处理得到数组 nums 中任意两个数的最大公约数，存储在二维数组 g 中，
其中 g[i][j] 表示 nums[i] 和 nums[j] 的最大公约数。
然后定义 f[k] 表示当前操作后的状态为 k 时，可以获得的最大分数和。
假设 m 为数组 nums 中的元素个数，那么状态一共有 2^m 种，即 k 的取值范围为 [0, 2^m - 1]
从小到大枚举所有状态，对于每个状态 k，先判断此状态中二进制位的个数 cnt 是否为偶数，是则进行如下操作：
枚举 k 中二进制位为 1 的位置，假设为 i 和 j，则 i 和 j 两个位置的元素可以进行一次操作，
此时可以获得的分数为 cnt/2 × g[i][j]，更新 f[k] 的最大值。
最终答案即为 f[2^m - 1]。
'''
class Solution:
def maxScore(self, nums: List[int]) -> int:
m = len(nums)
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])
f = [0] * (1 << m)
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]