力扣第397场周赛

A

记录每个字母的位置即可。

class Solution {
public:
    int findPermutationDifference(string s, string t) {
        int pos1[26] = {0}, pos2[26] = {0};
        for (int i = 0; i < s.size(); i++) pos1[s[i] - 'a'] = i;
        for (int i = 0; i < t.size(); i++) pos2[t[i] - 'a'] = i;
        int ans = 0;
        for (int i = 0; i < 26; i++) ans += abs(pos1[i] - pos2[i]);
        return ans;
    }
};

B

一眼dp题目

1
2
3

设从 i 出发的得分为 f(i)，则递推式为 f(i)=f(i+k)+a

算出所有 f(i)的值后取最大的即可

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        int n = energy.size();
        long long f[n];
        for (int i = n - 1; i >= 0; i--) {
            f[i] = energy[i];
            if (i + k < n) f[i] += f[i + k];
        }
        long long ans = -1e18;
        for (int i = 0; i < n; i++) ans = max(ans, f[i]);
        return ans;
    }
};

C

脑经急转弯dp

题意就是找到一个点左上方的另一个点，求解他们的最大值差

枚举终点，然后求解起点的最小值，用dp去递推即可。

class Solution {
public:
    int maxScore(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        long long f[n][m];
        long long ans = -1e18;
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++) 
        {
            long long mn = 1e18;
            if (i > 0) mn = min(mn, f[i - 1][j]);
            if (j > 0) mn = min(mn, f[i][j - 1]);
            ans = max(ans, grid[i][j] - mn);
            f[i][j] = min(1LL* grid[i][j], mn);
        }
        return ans;
    }
};