Leetcode1799. Maximize Score After N Operations

You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.

In the ith operation (1-indexed), you will:

Choose two elements, x and y.
Receive a score of i * gcd(x, y).
Remove x and y from nums.

Return the maximum score you can receive after performing n operations.

The function gcd(x, y) is the greatest common divisor of x and y.

Example 1:

Input: nums = [1,2]
Output: 1
Explanation: The optimal choice of operations is:
(1 * gcd(1, 2)) = 1

Example 2:

Input: nums = [3,4,6,8]
Output: 11
Explanation: The optimal choice of operations is:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

Example 3:

Input: nums = [1,2,3,4,5,6]
Output: 14
Explanation: The optimal choice of operations is:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

状态压缩dp，代码很好懂
``C++
class Solution {
public:

vector<int> num;
vector<int> f;
vector<vector<int>> gcd;
int n, maxstate;

int dfs(int state, int t) {
    if (f[state] != -1)
        return f[state];
    f[state] = 0;
    for (int i = 0; i < n; i ++)
        for (int j = i+1; j < n; j ++) {
            if (!(state & (1 << i)) || !(state & (1 << j)))
                continue;
            int v = t * gcd[i][j];
            int newstate = state - (1 << i) - (1 << j);
            f[state] = max(f[state], dfs(newstate, t+1) + v);
        }
    return f[state];
}

int maxScore(vector<int>& nums) {
    this->num = nums;
    n = nums.size();
    maxstate = 1 << n;

    f.assign(maxstate, -1);

    // 预处理gcd
    gcd.assign(n, vector<int>(n));
    for (int i = 0; i < n; i ++)
        for (int j = i+1; j < n; j ++)
            gcd[i][j] = __gcd(nums[i], nums[j]);

    return dfs(maxstate-1, 1);
}

};


也可以用bfs的方法，把状态变成一个图
```C++
class Solution {
public:

    vector<int> num;
    vector<int> f;
    vector<vector<int>> gcd;
    int n, maxstate;

    int bfs() {
        using pii = pair<int, int>;
        queue<pii> q;
        vector<bool> vis(maxstate, false);
        q.push({0, 1});
        f[0] = 0;

        while(!q.empty()) {
            printf("aaa %d\n", maxstate);
            pii p = q.front();
            q.pop();
            int state = p.first;
            int t = p.second;
            if (vis[state])
                continue;
            vis[state] = true;
            for (int i = 0; i < n; i ++)
                for (int j = i+1; j < n; j ++) {
                    if ((state & (1 << i)) || (state & (1 << j)))
                        continue;
                    int newstate = state | (1 << i) | (1 << j);
                    int score = t * gcd[i][j];
                    if (f[state] + score > f[newstate]) {
                        f[newstate] = f[state] + score;
                        q.push({newstate, t+1});
                    }
                }
        }
        return f[maxstate-1];
    }

    int maxScore(vector<int>& nums) {
        this->num = nums;
        n = nums.size();
        maxstate = 1 << n;

        f.assign(maxstate, -1);

        // 预处理gcd
        gcd.assign(n, vector<int>(n));
        for (int i = 0; i < n; i ++)
            for (int j = i+1; j < n; j ++)
                gcd[i][j] = __gcd(nums[i], nums[j]);

        return bfs();
    }
};