G - Meeting Room Arrangement UVALive - 6606——动态规划

忘是亡心i 2022-06-11 05:47 29阅读 0赞

Think:  
1知识点：动态规划  
2题目分析：会议室0~10时可开会，输入最多20组开会起止时间，询问可安排的最大开会数量  
3思路：  
1>动态规划——线性时间规划  
2>数据量最多20组开会起止时间，可暴力枚举状态选择最优解

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    struct Node{
        int s;
        int f;
    }node[24];
    
    bool cmp(struct Node a, struct Node b){
        if(a.s != b.s)
            return a.s < b.s;
        else
            return a.f < b.f;
    }
    
    int main(){
        int T, i, j, mav, s, f, t, dp[24];
        scanf("%d", &T);
        while(T--){
            t = 0;
            while(scanf("%d %d", &s, &f) && (s || f)){
                node[t].s = s, node[t].f = f, t++;
            }
            sort(node, node+t, cmp);
            memset(dp, 0, sizeof(dp));
            for(i = 0; i < t; i++){
                mav = 0;
                for(j = 0; j < i; j++){
                    if(node[j].f <= node[i].s && dp[j] > mav){
                        mav = dp[j];
                    }
                }
                dp[i] = mav + 1;
            }
            mav = 0;
            for(i = 0; i < t; i++){
                mav = max(mav, dp[i]);
            }
            printf("%d\n", mav);
        }
        return 0;
    }

[vjudge]: https://vjudge.net/contest/174571#problem/G

发表评论取消回复

表情：

评论列表（有 0 条评论，29人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode Top 100 Liked Questions 253. Meeting Rooms II (Java版； Medium)

[welcome to my blog][] LeetCode Top 100 Liked Questions 253. Meeting Rooms II (Java版

「爱情、让人受尽委屈。」/ 2023年07月03日 07:22/ 0 赞/ 24 阅读

相关动态规划

一：概念：和分冶法相似，不同之处在于前者是把问题划分为互不相交的子问题，而动态规划会出现子问题重叠的情况。通常用来求解最优化问题。。基本步骤： ①：刻画一个最优

我就是我/ 2022年12月01日 11:51/ 0 赞/ 21 阅读

相关动态规划

-------------------- 动态规划的设计思想动态规划（DP）\[1\]通过分解成子问题解决了给定复杂的问题，并存储子问题的结果，以避免再次计算相同的结

柔情只为你懂/ 2022年09月25日 11:15/ 0 赞/ 253 阅读

相关动态规划

作者：Hawstein 出处： [http://hawstein.com/posts/dp-novice-to-advanced.html][http_hawstein.c

淡淡的烟草味﹌/ 2022年09月24日 12:17/ 0 赞/ 200 阅读

相关动态规划

1. 首先，动态规划不是一个特定的算法，它代表的是一种思想，一种手段 2. 动态规划方法往往用于求解“最优化问题”，能用动态规划求解的问题的前提是问题具有“最优子结构性质”

刺骨的言语ヽ痛彻心扉/ 2022年07月29日 11:46/ 0 赞/ 87 阅读

相关 Facebook面试题 meeting rooms 求同时最多meeting room的时间

> 给出会议开始和结束时间，求meeting room interval最多的时间点。返回任意一个时间即可。显然本题可以方便地使用扫描线算法解决。在扫描线段的同时保存

超、凢脫俗/ 2022年07月13日 11:26/ 0 赞/ 26 阅读

相关 G - Meeting Room Arrangement UVALive - 6606——动态规划

Think: 1知识点：动态规划 2题目分析：会议室0~10时可开会，输入最多20组开会起止时间，询问可安排的最大开会数量 3思路： 1>动态规划——线性时间规

忘是亡心i/ 2022年06月11日 05:47/ 0 赞/ 30 阅读

相关动态规划

基本思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。区别：与

ゞ浴缸里的玫瑰/ 2022年05月25日 09:44/ 0 赞/ 443 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 322 阅读

相关动态规划

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/7519359

左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 493 阅读