Luobuyu's Blog

0%

1494. 并行课程II

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.9k 阅读时长 ≈ 2 分钟
使用状态压缩，然后枚举子集进行dp。

1494.并行课程II

题目描述：

给出 $n$ 个课程，编号 $1$ 到 $n$ ， $relations[i] = [x_i,y_i]$ 表示一个先修课关系，课程 $x_i$ 必须在课程 $y_i$ 之前上完。同时还给出一个整数 $k$ 。

在一个学期中，最多可以同时上 $k$ 门课，前提是这些课的先修课在之前的学期已经上过。

请返回上完所有课最少需要多少个学期。保证存在一种方式上完所有的课程。

数据范围：

$1\le n \le 15, 1\le k \le n$

题解：

二进制子集枚举：

1
2
3
4
// 降序遍历 x 的非空子集
for (int sub = x; sub; sub = (sub - 1) & x) {
    // sub 是 x 的一个非空子集
}

最后的子集是空集，如果需要特殊处理需要跳出循环。

状压dp：

使用二进制来表示需要上哪些课，使用 $need[i]$ 表示课程 $i$ 的前置课程， $dp[i]$ 表示学完课程集合 $i$ 所需要的最少学期数。那么可以得到状态转移方程

也就是枚举集合 $[0, 1 << n)$ ，然后对于状态 $i$ 需要找到任意一个子集 $sub$ （因为比 $i$ 小的， $i$ 的子集都已经被算出来了，因此只需要找任意一个子集就行）。可以找 sub1 = i & (i - 1), sub2 = i ^ sub1，并且刚好 sub2 = i & (-i)，就是树状数组里面的原酸，用于找到最低位的 $1$ 。

当前学期学习 i ^ need[i]，need[i] 必须在之前的学期完成，否则不能学习 $i$ 。因此判断是否合法，i | need[i] == i时才合法。当前学期学习 valid = i ^ need[i]，如果 $valid$ 中 $1$ 的个数小于等于 $k$ ，那么本学期可以直接学完，更新 dp[i] = min(dp[i], dp[i ^ valid] + 1)。因为当前学期学习 $valid$ ，那么之前的学期学习的是 i ^ valid。如果 $valid$ 中 $1$ 的个数大于 $k$ ，那么需要枚举 $valid$ 的子集 $sub$ ，对于 $1$ 的个数小于等于 $k$ 的子集，更新 dp[i] = min(dp[i], dp[i ^ sub] + 1)。最后返回 $dp[(1 << n) - 1]$ 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    static const int maxn = 1e5 + 10;
    int dp[maxn] = {};
    int need[maxn] = {};
    int minNumberOfSemesters(int n, vector<vector<int>> &relations, int k)
    {
        for (auto &edge : relations)
        {
            int u = edge[0] - 1;
            int v = edge[1] - 1;
            need[(1 << v)] |= (1 << u);
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for (int i = 1; i < (1 << n); ++i)
        {
            int set1 = i & (-i);
            int set2 = i ^ set1;
            need[i] = need[set1] | need[set2];
            if ((need[i] | i) != i)
                continue;

            int valid = i ^ need[i];
            if (__builtin_popcount(valid) <= k)
            {
                dp[i] = min(dp[i], dp[i ^ valid] + 1);
            }
            else
            {
                for (int sub = valid; sub; sub = valid & (sub - 1))
                {
                    if (__builtin_popcount(sub) <= k)
                    {
                        dp[i] = min(dp[i], dp[i ^ sub] + 1);
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};