Leet Code Weekly Contest 297

class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        double ans = 0;
        for (int i = brackets.size() - 1; i > 0; i--) {
            brackets[i][0] -= brackets[i - 1][0];
        }
        for (auto &b : brackets) {
            int d = min(income, b[0]);
            ans += 0.01 * d * b[1];
            income -= d;
        }
        return ans;
    }
};

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid.front().size(), ans = INT_MAX;
        vector<vector<int>> f(m, vector<int>(n, INT_MAX));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    f[i][j] = grid[i][j];
                }
                if (i + 1 < m) {
                    for (int k = 0; k < n; k++) {
                        f[i + 1][k] = min(f[i + 1][k], f[i][j] + moveCost[grid[i][j]][k] + grid[i + 1][k]);
                    }
                } else {
                    ans = min(ans, f[i][j]);
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int distributeCookies(vector<int>& cookies, int k) {
        int n = cookies.size();
        vector<int> g(1 << n, 0);
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    g[mask] += cookies[i];
                }
            }
        }
        vector<vector<int>> f(k, vector<int>(1 << n, INT_MAX));
        for (int i = 0; i < k; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                if (i == 0) {
                    f[i][mask] = g[mask];
                } else {
                    for (int mask2 = 0; mask2 < (1 << n); mask2++) {
                        if ((mask & mask2) == mask2) {
                            f[i][mask] = min(f[i][mask], max(g[mask2], f[i - 1][mask - mask2]));
                        }
                    }
                }
            }
        }
        return f[k - 1][(1 << n) - 1];
    }
};

typedef long long ll;

class Solution {
public:
    ll distinctNames(vector<string>& ideas) {
        unordered_set<string> ideaSet(ideas.begin(), ideas.end());
        unordered_map<char, vector<string>> c2s;
        for (auto &s : ideas) {
            c2s[s[0]].push_back(s);
        }
        vector<vector<int>> f(26, vector<int>(26));
        for (char x = 'a'; x <= 'z'; x++) {
            for (char y = 'a'; y <= 'z'; y++) {
                for (auto &s : c2s[x]) {
                    string s2 = s;
                    s2[0] = y;
                    if (ideaSet.count(s2) == 0) {
                        f[x - 'a'][y - 'a']++;
                    }
                }
            }
        }
        ll ans = 0;
        for (char x = 'a'; x <= 'z'; x++) {
            for (char y = 'a'; y <= 'z'; y++) {
                ll p = f[x - 'a'][y - 'a'];
                ll q = f[y - 'a'][x - 'a'];
                ans += p * q;
            }
        }
        return ans;
    }
};