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

链接：1799.N次操作后的最大分数和
难度：Hard
标签：位运算、数组、数学、动态规划、回溯、状态压缩、数论
简介：请你返回 n 次操作后你能获得的分数和最大为多少。

题解 1 - cpp

• 编辑时间：2022-12-22
• 执行用时：52ms
• 内存消耗：7.6MB
• 编程语言：cpp
• 解法介绍：不能贪心，利用二进制状态压缩考虑每一种情况进行动态规划。

class Solution {
public:
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    int cnt1(int num) {
        int cnt = 0;
        for (; num; num >>= 1) if (num & 1) cnt++;
        return cnt;
    }
    int mgcd[20][20], dp[20000] = {0};
    int maxScore(vector<int>& nums) {
        int n = nums.size(), allused = (1 << n) - 1;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                mgcd[i][j] = mgcd[j][i] = gcd(nums[i], nums[j]);
            }
        }
        for (int used = 1; used <= allused; used++) {
            int cnt = cnt1(used);
            if (cnt & 1) continue;
            for (int i = 0; i < n; i++) {
                if ((used & (1 << i)) == 0) continue;
                for (int j = i + 1; j < n; j++) {
                    if ((used & (1 << j)) == 0) continue;
                    dp[used] = max(dp[used], dp[used ^ (1 << i) ^ (1 << j)] + cnt / 2 * mgcd[i][j]);
                }
            }
        }
        return dp[allused];
    }
};