LYX的代码能力恢复计划

一年没写代码的LYX已经是个废人了。

现在开始每周打lc恢复恢复实力。。

给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。

在第 i 次操作时（操作编号从 1 开始），你需要：

选择两个元素 x 和 y 。 获得分数 i * gcd(x, y) 。 将 x 和 y 从 nums 中删除。

请你返回 n 次操作后你能获得的分数和最大为多少。

函数 gcd(x, y) 是 x 和 y 的最大公约数。

这是一个简单的状压模板题，以前做了一万道的那种。。现在我只会想暴力了竟然。。。

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int len = nums.size();
        vector<int>dp((1 << len) +1, 0);
        for (int i = 0; i < (1 << len) - 1; i++) {
            bitset<20>now(i);
            if (now.count() % 2)continue;
            for (int j = 0; j < len; j++) {
                for (int k = j + 1; k < len; k++) {
                    if (now[j] != 0 || now[k] != 0)continue;
                    int newpos = i + (1 << j) + (1 << k);
                    dp[newpos] = max(dp[newpos], dp[i] + gcd(nums[j], nums[k]) * ((int)now.count() / 2 + 1));
                }
            }
        }
        return dp[(1 << len) - 1];
    }
};