4. 并行课程 II

思路

【状态压缩】

看到数据范围很小,考虑状态压缩。再加上在枚举某一门课是否可以上的时候,确实需要其他课的信息才能判断。

【整体思路】

dp[state] 表示上课状态为 state 时所需要的最少学期数。第一维枚举当前状态 state ,对于这个状态开始暴搜,暴搜前统计在当前 state 下可以上的课程(去除掉 state 中已有的课程 & 不符合先序关系的课程)。

代码

int dp[1<<16];
vector<int> pred[20];
class Solution {
public:
    void dfs(vector<int>& course, int num, int now, int state, int id) {
        if(num == 0 || now >= course.size()) {
            if(dp[state] == -1 || dp[state] > id) dp[state] = id;
            return;
        }
        dfs(course, num-1, now+1, state|(1<<course[now]), id);
        dfs(course, num, now+1, state, id);
    }

    int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
        int lim = (1 << n) - 1;
        for(int i=0; i<=lim; i++) dp[i] = -1;
        dp[0] = 0;
        for(int i=0; i<n; i++) pred[i].clear();

        for(auto x: dependencies) pred[x[1]-1].push_back(x[0]-1);
        
        for(int s=0; s<=lim; s++) {
            if(dp[s] == -1) continue;
            vector<int> course;
            for(int i=0; i<n; i++) {
                if((s >> i) & 1) continue;
                bool flag = true;
                for(auto x: pred[i]) {
                    if((s >> x) & 1) continue;
                    flag = false; break;
                }
                if(!flag) continue;
                course.push_back(i);
            }
            int m = course.size();
            dfs(course, min(k, m), 0, s, dp[s]+1);
        }
        return dp[lim];
    }   
};
最后修改:2020 年 08 月 23 日 01 : 23 PM
如果觉得我的文章对你有用,请随意赞赏