第 397 场 LeetCode 周赛题解

模拟：遍历 $s$ 记录各字符出现的位置，然后遍历 $t$ 计算排列差

class Solution {public:int findPermutationDifference(string s, string t) {int n = s.size();vector<int> loc(26);for (int i = 0; i < n; i++)loc[s[i] - 'a'] = i;int res = 0;for (int i = 0; i < n; i++)res += abs(loc[t[i] - 'a'] - i);return res;}
};

模拟：设 $p[i]$ 为从 $i$ 出发能获得的最大能量，逆序遍历 $energy$ 求 $p$

class Solution {public:int maximumEnergy(vector<int>& energy, int k) {int n = energy.size();vector<int> p(n);for (int i = n - 1; i >= 0; i--)p[i] = i + k < n ? p[i + k] + energy[i] : energy[i];return *max_element(p.begin(), p.end());}
};

前缀极值：可以发现一条移动路径的得分只和路径的终点和起点有关，所以当终点固定为 $grid[i][j]$ 时，起点值为 $grid[0,i][0,j]$ 中非 $grid[i][j]$ 的最小值时得分最大。所以枚举终点，用二维前缀维护子矩阵中非 $grid[i][j]$ 的最小值。

class Solution {public:int maxScore(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();int mn[m][n];int res = INT32_MIN;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (i == 0) {mn[i][j] = j == 0 ? grid[i][j] : min(mn[i][j - 1], grid[i][j]);if (j != 0)res = max(res, grid[i][j] - mn[i][j - 1]);} else {mn[i][j] = j == 0 ? min(mn[i - 1][j], grid[i][j]) : min({mn[i - 1][j], mn[i][j - 1], grid[i][j]});if (j != 0)res = max(res, grid[i][j] - min(mn[i - 1][j], mn[i][j - 1]));elseres = max(res, grid[i][j] - mn[i - 1][j]);}}return res;}
};

状态压缩：根据分数计算公式，有一个重要的结论是：把 $perm$ 看成一个环，在环上选择不同位置作为数组起点可以得到不同的 $perm$ 数组，但这些 $perm$ 数组的分数是相同的，所以要想字典序最小，$perm$ 首位为 $0$ 。设 $p[cur][pi]$ 为“当前各数的使用状态为 $cur$ （若$cur>>i\&1$ 则 $i$ 已使用），$perm$ 下一位为 $pi$ ”的情况下，接下来能够获得的最大得分。通过记忆化搜索实现状态转移求 $p[0][0]$ , 同时用数组间接记录状态转移的路径。

class Solution {public:vector<int> findPermutation(vector<int>& nums) {int n = nums.size();int N = 1 << n;vector<vector<int>> p(N, vector<int>(n, -1));//-1：初始化标志vector<vector<int>> select(N, vector<int>(n, -1));//数组间接记录状态转移的路径function<int(int, int, int)> get = [&](int cur, int pi, int ind) {if (p[cur][pi] != -1)return p[cur][pi];if (ind == n - 1)//pi为perm的最后一个元素return p[cur][pi] = abs(pi - nums[0]);p[cur][pi] = INT32_MAX;for (int np = 0; np < n; np++)if ((cur >> np & 1) == 0 && np != pi)//枚举perm中pi的后一个元素npif (abs(pi - nums[np]) + get(cur | (1 << pi), np, ind + 1) < p[cur][pi]) {p[cur][pi] = abs(pi - nums[np]) + get(cur | (1 << pi), np, ind + 1);select[cur][pi] = np;//记录路径}return p[cur][pi];};get(0, 0, 0);vector<int> res;int new_mask, new_cur;for (int cur = 0, mask = 0; res.size() < n; mask = new_mask, cur = new_cur) {//重现路径res.push_back(cur);new_mask = mask | (1 << cur);new_cur = select[mask][cur];}return res;}
};