P1986 元旦晚会

    • 31通过
    • 109提交
  • 题目提供者 lyx613
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 模拟 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    玛雅人预言的世界末日没有发生,我们迎来了地球的第五个太阳纪。

    学校将要举办第五个太阳纪的第一次元旦晚会。Brett的班级要参加,并且还表演节目。

    题目描述

    Brett 班的节目是这样的:全班 n个同学排成一排,同学们手拿话筒,齐唱《喜洋洋与灰太狼》。(这个节目看起来有点二) 。

    Brett班的同学分成了m个声部,一个声部由连续的同学组成,第i个声部由a[i]到b[i]之间的同学组成(包括a[i] b[i])

    但是一个同学有可能同时属于多个声部,且有可能有同学不属于任何一个声部。 为了保证演唱效果,第 i 个声部必须至少有c[i]个同学持有话筒。(即第i个声部持有话筒的同学数大于等于 c[i])

    请你算出Brett班最少需要几个话筒。

    输入输出格式

    输入格式:

    第一行 2 个正整数 n,m

    以下m行,每行3个正整数 a[i] b[i] c[i]

    输出格式:

    一个正整数 满足要求的最少话筒数

    输入输出样例

    输入样例#1: 复制
    11 5 
    3 7 3 
    8 10 3 
    6 8 1 
    1 3 1 
    10 11 1 
    输出样例#1: 复制
    6 

    说明

    n<=30000 m<=5000

    1≤a[i]<b[i]≤n ;c[i]≤b[i]-a[i]+1

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。