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

Difficulty: 困难

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

提示:

解法一

48th 双周赛 t4,比较简单,看数据范围就知道是状压 DP,一开始写了个二维的状态,包含了当前操作的次数,以及选取状态,结果 t 了。忘记考虑的复杂度了,后面对做了预处理优化勉强过了,但是依然比较慢

重新思考了递推状态,发现当前操作次数这个状态其实是没有必要的,这个状态可以通过的二进制的位数推断出来,所以状态变为,代表经过次操作,选取的元素掩码为时的最大得分

  • 入口:
  • 转移:,枚举所有偶数个的状态,然后枚举所有数对,确保包含,然后递推取最大值
  • 出口:,时间复杂度为数组长度

代码实现如下:

import java.util.*;

class Solution {

public int maxScore(int[] nums) {
int len = nums.length;
int n = len/2;
int[] dp = new int[2<<len];
int[][] cache = new int[len][len];
for (int i = 0; i < len; i++) {
for (int j = i+1; j < len; j++) {
cache[i][j] = gcd(nums[i], nums[j]);
}
}
for (int s = 0; s < (1<<len); s++) {
int cnt = countBit(s);
// 选取个数一定是偶数
if ((cnt&1)==1) continue;
for (int j = 0; j < len; j++) {
//s 必须选取 j, k
if (((s>>>j)&1)==0) continue;
for (int k = j+1; k < len; k++) {
if (((s>>>k)&1)==0) continue;
dp[s] = Math.max(dp[s], (countBit(s)/2)*cache[j][k] + dp[s^(1<<j)^(1<<k)]);
}
}
}
return dp[(1<<len)-1];
}

public int countBit(int a) {
int cnt = 0;
while (a != 0) {
a = a&(a-1);
cnt++;
}
return cnt;
}

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

解法二

题解区看到的另一种写法,直接枚举的子集,思路挺好,但是时间复杂度略高,是掩码中的个数,最多可能是

public int maxScore2(int[] nums) {
int len = nums.length;
int n = len/2;
int[] dp = new int[2<<len];
for (int i = 0; i < len; i++) {
for (int j = i+1; j < len; j++) {
dp[(1<<i)|(1<<j)] = gcd(nums[i], nums[j]);
}
}
//2^len
for (int s = 0; s < (1<<len); s++) {
//2^k k 是 s 中 1 的个数
for (int i = s; i != 0; i=(i-1)&s) {
if (countBit(s)-countBit(i)==2) {
dp[s] = Math.max(dp[s], countBit(s)/2*dp[s^i]);
}
}
}
return dp[(1<<len)-1];
}