Day 30 状态压缩, 拓扑排序

31. 状态压缩

题目描述：n integers from 1 to n, permutate, either: perm[i] % i == 0 or i % perm[i] == 0

class Solution {
public:
    int countArrangement(int n) {
        vector<int> f(1 << n);
        f[0] = 1;
        // 遍历所有可能情况
        for (int mask = 1; mask < (1 << n); mask++) {
            //被选中的个数
            int num = __builtin_popcount(mask);
            for (int i = 0; i < n; i++) {
                //第i + 1位数被选中 && 可以被放到最高位上
                if (mask & (1 << i) && (num % (i + 1) == 0 || (i + 1) % num == 0)) {
                    // 加上剩余n-1个数的可能排序方式的个数
                    f[mask] += f[mask ^ (1 << i)];
                }
            }
        }
        return f[(1 << n) - 1];
    }
};

1255. Maximum Score Words Formed by Letters

题目描述：Given list of words, and list of single letters and score of every character, return maximum score of any valid set of words formed by the letters given. Each letter can only be used once.

思路：统计提供的字母次数遍历所有可能情况，for (int s = 1; s < (1 << n); s++) { 统计子集中所有字母出现的次数如果次数都没有超过提供的次数，将当前和与最大和比较，更新最大和

class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        int n = words.size(), res = 0;
        vector<int> count(26);
        for (auto c : letters) {
            count[c - 'a']++;
        }
        for (int s = 1; s < (1 << n); s++) {
            vector<int> wordCount(26); // 统计子集 s 所有单词的字母数目
            for (int k = 0; k < n; k++) {
                if ((s & (1 << k)) == 0) { // words[k] 不在子集 s 中
                    continue;
                }
                for (auto c : words[k]) {
                    wordCount[c - 'a']++;
                }
            }
            bool ok = true; // 判断子集 s 是否合法
            int sum = 0; // 保存子集 s 的得分
            for (int i = 0; i < 26; i++) {
                sum += score[i] * wordCount[i];
                ok = ok && (wordCount[i] <= count[i]);
            }
            if (ok) {
                res = max(res, sum);
            }
        }
        return res;
    }
};

30: 拓扑排序

1976. Number of Ways to Arrive at Destination

题目描述：Given integer n, and 2D array roads where roads[i] = [u_i, v_i, time_i], meaning there is a road between u_i, and v_i, that takes time_i to travel, return the number of ways can travel from 0 to n - 1 in the sortest amount of time, return ans % (10⁹ + 1)

思路：性质：在任意的合法方案中，途径的该路径中的每个点时，都是以最短路径的方式到达的在跑「拓扑排序」过程中进行 DP，统计方案数

//dijkstra
while (!pq.empty()) {
    auto [_, u] = pq.top();
    pq.pop();
    if (vis[u]) {
        continue;
    }
    vis[u] = 1;
    for (auto [v, w]: G[u]) {
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            f[v] = f[u];
            pq.push({dist[v], v});
        } else if (dist[v] == dist[u] + w) {
            f[v] = (f[u] + f[v]) % (long)(1e9 + 7);
        }
    }
}