双周赛 – 29 – 并行课程 II

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];
    }   
};

评论

  1. 1年前
    2020-6-29 17:45:48

    VineAsh 太强啦|´・ω・)ノ

    • vineash 博主
      1年前
      2020-6-29 20:35:16

      VineAsh太菜了。不考机试VineAsh连写题解的动力都没有了>﹏<。

  2. 1年前
    2020-6-29 17:45:48

    VineAsh 太强啦|´・ω・)ノ

    • vineash 博主
      1年前
      2020-6-29 20:35:16

      VineAsh太菜了。不考机试VineAsh连写题解的动力都没有了>﹏<。

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇